Periodically externally hereditary permutation automata

A. V. Babash


Abstract: We suggest an algorithm which checks the following property of a given finite permutational automaton: for any periodic input sequence and any initial state the period of the corresponding output sequence is divided by the period of the input sequence. Estimates of the complexity of such algorithms are given.

UDC: 519.7

Received: 05.06.2003

DOI: 10.4213/dm116

 English version: Discrete Mathematics and Applications, 2005, 15:6, 599–610

Bibliographic databases:

• 
• 
•