Principal Ideal Languages and Synchronizing Automata

Issue title: Russian-Finnish Symposium in Discrete Mathematics

Article type: Research Article

Authors: Gusev, Vladimir V. | Maslennikova, Marina I. | Pribavkina, Elena V.

Affiliations: Institute of Mathematics and Computer Science, Ural Federal University, Lenina st. 51, Ekaterinburg 620083, Russia. [email protected], [email protected], [email protected]

Note: [] Address for correspondence: Ural Federal University, 620083, Lenina st. 51, Ekaterinburg, Russia

Abstract: We study ideal languages generated by a single word. We provide an algorithm to construct a strongly connected synchronizing automaton for which such a language serves as the language of synchronizing words. Also we present a compact formula to calculate the syntactic complexity of this language.

Keywords: ideal language, synchronizing automaton, synchronizing word, strongly connected automaton, syntactic complexity

DOI: 10.3233/FI-2014-1034

Journal: Fundamenta Informaticae, vol. 132, no. 1, pp. 95-108, 2014