2019 year, volume 23, issue 3 (PDF)

Menkin M. Auto-translation of rules of the road to formal graph-theoretic model

The present article deals with semantic analysis of legal documents. In this paper, we introduce one possible approach to formal modeling of rules of the road. We describe the basic procedures for semantic analysis of one type of sentences.

Keywords: semantic analysis of legal documents, pragmatic analysis, modeling of text semantic.

Bokov G.V. Graph based extended resolution for Boolean formulas

In this article we consider a graph based extended resolution for representing refutations of Boolean formulas in conjunction normal form. We prove that a Boolean formula is unsatisfiable iff there is its graph based refutation.

Keywords: Resolution, graph based refutation, unsatisfiability, Boolean formulas.

Eremenko A.R., Yashunsky A.D. On the weight of functions, defined by read-once AND/OR formulas

We consider the set of functions defined by read-once formulas with binary conjunction (logical AND) and disjunction (logical OR) operations. For the functions defined by formulas with a fixed number of operations we investigate the weights of functions, i.e. the number of tuples on which the function has value 1. We establish asymptotic bounds on the number of read-once formulas that define functions with specific weights, in particular on the number of formulas, that define functions with no more than a quarter of ones among their values.

Keywords: Boolean function, read-once formula, function weight, asymptotic bound.

V.N. Kozlov Codes that define images accurate to affine transformations

The paper presents codes that define images with an accuracy of affine transformations, including some new code.

Keywords: pattern recognition, images, image codes.

Sitdikov T. R. The complexity of multidimensional rectangular circuits design

A model of rectangular multidimensional circuits is considered in this paper. Logic gates are placed in cells of d-dimensional mesh. Each pair of adjacent cells is connected by a bus with at most k wires. We establish Shannon function upper bound \( \frac{2^n}{\min(n,d \log{k})} \) for the complexity of this type of circuits.

Keywords: multidimensional circuits, multilayer circuits, Shannon function asymptotics, circuit complexity.

Chasovskikh A.A. On the number of maximum overclasses in the linear automata class

Updated maximale subclasses lists in linear automata classes over finite fields. A criterion is found for the finiteness of the number of precomplete overclasses for a given set of linear automata.

Keywords: finite automaton, linear automaton, operation of composition, feedback, completeness, closed class, maximum subclass, finite field.

Babin D.N. Automata with linear transition functions

The problem of completeness of the system of automaton functions with linear transitions with respect to the operation of superposition is considered. This system is not complete; moreover, any system of automata that complements it to the basis is infinite.

Keywords: finite automaton, completeness, superposition, closed class.

Popkov K.A. Short single fault detection tests for contact circuits under breaks and closures of contacts

We consider a problem of implementation of Boolean functions by irredundant two-pole contact circuits which allow short single fault detection tests regarding breaks and closures of contacts. We describe all functions which the minimal length of such a test equals 0, 1, 2, and 3 for. We prove that, for almost all Boolean functions on n variables, this length equals 4.

Keywords: contact circuit, Boolean function, contact break, contact closure, fault detection test.

Konovalov A.Yu. The intuitionistic set theory is not sound with respect to the constructive sematics based on hyperarithmetic sorts.

The soundness of axioms of the intuitionistic set theory with respect to the realizability semantics based on hyperarithmetical sorts is studied.

Keywords: constructive semantics, realizability, axiomatic set theory, hyperarithmetical sorts.

Chasovskikh A.A. On classes of transfer functions of linear automata

For classes of transfer functions of linear automata over a finite field with operations induced by composition operations on these automata, all maximal subclasses are found.

Keywords: finite automaton, linear automaton, transfer function, operation of composition, feedback, completeness, closed class, maximum subclass, finite field.

Reports of the seminar "Theory of Automata"

← Back to archive