This article is cited in 2 papers

Linearly realizable automata

S. B. Rodin

Lomonosov Moscow State University

Abstract: The paper is devoted to the investigation of “linearly realizable” automata, i.e. automata that allow state encodings that lead to implementations with linear Boolean operators. We formulate the criterion of linear realizability and obtain upper and lower bounds on the number of linearly realizable automata.

Keywords: automata theory, automata, semiautomata, transition systems, permutation, substitution function, assignment, state encoding, complexity.

UDC: 519.713.1

Received: 21.11.2016

DOI: 10.4213/dm1406

 English version: Discrete Mathematics and Applications, 2017, 27:6, 387–402

Bibliographic databases:

• 
• 
•