English
2018 год, том 22 выпуск 1 (PDF)
В работе рассматривается класс нейронных кусочно-параллельных функций с двоично-рациональными коэффициентами. Доказано что для любой функции из класса кусочно-параллельных функций существует функция из класса кусочно-параллельных функций с двоично-рациональными коэффициентами, приближающая ее с наперед заданной точностью. Также, для рассматриваемого класса функций показано, что существуют базисы, состоящие из заданного (произвольного) числа элементов, в частности, найдена Шефферова функция.
Ключевые слова: класс кусочно-параллельных функций, класс нейронных функций с двоично-рациональными коэффициентами, операции суперпозиции, Шефферова функция, базисы.
В работе анализируются всевозможные латинские квадраты порядка 4, порождаемые с помощью правильных семейств функций. Оказывается, что все такие квадраты задают квазигруппы, не являющиеся полиномиально полными. Предлагается обобщение конструкции, связанной с правильными семействами. В результате удается в 4 раза увеличить число порождаемых латинских квадратов и получить значительное число полиномиально полных квазигрупп.
Ключевые слова: Квазигруппа, латинский квадрат, параметрическое задание, полиномиальная полнота, правильные семейства функций.
Известно, что автоматы с магазинной памятью сохраняют множество периодических последовательностей. Ранее автор привёл верхние и нижние оценки на максимальный период выходной последовательности автономного автомата с магазинной памятью в зависимости от характеристик автомата. В данной работе приводятся оценки на максимальный период выходной последовательности для общего случая. Период выходный последовательности был изучен главным образом как функция от периода входной последовательности.
Ключевые слова: автомат с магазинной памятью, детерми-нированная функция, периодические последовательности.
В статье исследуется связь между площадью и максимальным потенциалом плоских схем, реализующих булевы операторы. Максимальный потенциал мера сложности плоских схем, отражающая энергопотребление схемы в худшем случае, его также часто называется активностью. Он равен максимальному числу выходов элементов схемы, равных 1, где максимум берётся по всем входным наборам схемы. В работе показано, что для произвольного булева оператора потенциал \(\hat{U}\) не меньше, чем \(\sqrt{S} /4 \sqrt{2} \), где S - площадь минимальной схемы, реализующей данный оператор.
Ключевые слова: клеточные схемы, активность, потенциал, связь мер сложности, нижние оценки, булевы операторы.
Вопрос о сложности доказательств теорем в формальных системах возникает во многих областях. С точки зрения вычислительной сложности точные нижние оценки сложности доказательств служат средством отделения классов вычислительной сложности. В современных SAT- и SMT-решателях анализ лежащих в их основе систем доказательств позволяет оценить производительность и ограниченность решателей. Центральное место в вопросе сложности доказательств отводится доказательству теорем классического исчисления высказываний. Несмотря на то, что за последние десятилетия удалось разработать много разнообразных техник для доказательства верхних и нижних оценок в различных пропозициональных системах, успеха в получении нижних оценок для классических систем доказательств достичь так и не удалось. Тем не менее, среди специалистов в области сложности доказательств сложилась прочная уверенность в том, что существует тесная связь между прогрессом в получении нижних оценок сложности булевых схем и прогрессом в получении нижних оценок размера пропозициональных доказательств. В работе будет рассказано о связи между булевыми схемами и системами доказательств теорем, о том, как идеи и методы, применяемые для оценки сложности схем, применяются для оценки сложности доказательств теорем.
Ключевые слова: Системы пропозициональных доказательств, сложность доказательств, булевы схемы, сложность схем, классы сложности.
Традиционно считается, что при переходе от двузначного к многозначному случаю свойства решетки замкнутых классов функций координально меняются. В докладе будет показано, что несмотря на различия, эти решётки во многом похожи, а очень многие свойства, которые следуют из решетки Поста, могут быть обобщены на многозначный случай. Одним из таких примеров является решение задачи удовлетворения ограничениям для многозначного случая - показано, что самый общий полиномиальный алгоритм является во многом лишь комбинацией методов, давно известных для двузначного случая.
Ключевые слова: Булевы функции, k-значные функции, отношения, соответствие Галуа, задачи удовлетворения ограничениям.
Диагностические эксперименты с конечными автоматами впервые были описаны в классической работе Э. Мура, и с тех пор применяются для тестирования цифровых схем и коммуникационных протоколов. Одна из основных задач тестирования конечных автоматов состоит в определении начального состояния наблюдаемого автомата. Пусть имеется полное описание некоторого конечного автомата Мили, но про его начальное состояние известно лишь то, что оно принадлежит некоторому фиксированному подмножеству состояний. Тогда диагностическая задача состоит в нахождении начального состояния путем последовательной подачи входных символов на автомат. В данном докладе будет рассказано об оценках длины для таких последовательностей входных символов и показана связь данной задачи с комбинаторными проблемами, возникающими в теории гиперграфов.
Ключевые слова: конечный автомат, условный диагностиче-ский эксперимент, теорема Мура, гиперграф.