Principal Ideal Languages and Synchronizing Automata

• Autorzy: Gusev V. V. , Maslennikova M. I. , Pribavkina E. V.

Identyfikatory

DOI

10.3233/FI-2014-1034

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

ideal language; synchronizing automaton; synchronizing word; strongly connected automaton; syntactic complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 1
• Strony: 95--108
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Gusev V. V.

• Institute of Mathematics and Computer Science, Ural Federal University, Lenina st. 51, Ekaterinburg 620083, Russia

autor

Maslennikova M. I.

• Institute of Mathematics and Computer Science, Ural Federal University, Lenina st. 51, Ekaterinburg 620083, Russia

autor

Pribavkina E. V.

• Institute of Mathematics and Computer Science, Ural Federal University, Lenina st. 51, Ekaterinburg 620083, Russia

Bibliografia

• [1] Brzozowski, J., Ye, Y.: Syntactic Complexity of Ideal and Closed Languages. In G. Mauri, A. Leporati (Eds.) Proc. DLT 2011, Lect. Notes Comp. Sci. Vol. 6795, Springer-Verlag Berlin-Heidelberg 2011. P. 117–128.
• [2] Černý, J.: Poznámka k homogénnym eksperimentom s konečnými automatami., Mat.-Fyz. Cas. Slovensk. Akad. Vied. 14 (1964) 208–216.
• [3] Holzer, M., König, B.: On deterministic finite automata and syntactic monoid size. Theoret. Comput. Sci. 327 (2004) P. 319–347.
• [4] Maslennikova, M. I.: Reset Complexity of Ideal Languages. In M. Bieliková, G. Friedrich, G. Gottlob, S. Katzenbeisser, R. Špánek, G. Turán (eds.) Int. Conf. SOFSEM 2012, Proc. Volume II, Institute of Computer Science Academy of Sciences of the Czech Republic, 2012, P. 33–44.
• [5] Myhill, J.: Finite automata and representation of events. Wright Air Development Center Technical Report, 57624 (1957)
• [6] Perrin, D.: Finite automata. Handbook of Theoretical Computer Science, J. van Leewen, (ed.), Elsevier, B., P. 1–57, 1990.
• [7] Pribavkina, E., Rodaro, E.: Synchronizing automata with finitely many minimal synchronizing words// Inf. and Comput. V. 209(3), 2011. P. 568–579.
• [8] Pribavkina, E., Rodaro, E.: Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete// B. Löwe, D. Normann, I. Soskov, A. Soskova (Eds.) Proc. CiE 2011, Lect. Notes Comp. Sci. Vol. 6735, Springer-Verlag Berlin-Heidelberg 2011. P. 230–238.
• [9] Volkov, M. V.: Synchronizing automata and the Černý conjecture. In C. Martın-Vide, F. Otto, H. Fernau (eds.), Languages and Automata: Theory and Applications. LATA 2008. Lect. Notes Comp. Sci. 5196, Berlin, Springer (2008) 11–27.
• [10] Volkov, M. V.: Synchronizing automata preserving a chain of partial orders// In J. Holub and J. Ždárek (eds.) Implementation and Application of Automata. Proc. 12th Int. Conf. CIAA 2007, Lect. Notes Comp. Sci., Springer-Verlag, Berlin-Heidelberg-New York. 2007. V. 4783. P. 27–37.