Trim Strongly Connected Synchronizing Automata and Ideal Languages

• Autorzy: Maslennikova M. , Rodaro E.

Identyfikatory

DOI

10.3233/FI-2018-1720

• Konferencja: RuFiDiM Conference, Russian-Finnish Symposium in Discrete Mathematics (5; 16-19.05. 2017; Turku; Finland)
• Języki publikacji: EN

Abstrakty

EN

We follow language theoretic approach to synchronizing automata and Černý’s conjecture initiated in a series of recent papers. We prove that for every ideal language there exists a strongly connected synchronizing automaton from some special class for which given language serves as the language of reset words. This class is formed by trim automata recognizing left quotients of principal left ideal languages. We show that the minimal automaton recognizing a left quotient of a principal left ideal can be viewed as a synchronizing automaton for which given finitely generated ideal serves as the language of reset words.

Słowa kluczowe

EN

ideal language; synchronizing automaton; reset word; reset complexity; reset left regular decomposition; strongly connected automaton

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 162, nr 2/3
• Strony: 183--203
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Maslennikova M.

• Institute of Natural Sciences and Mathematics, Ural Federal University, Ekaterinburg, Russia

autor

Rodaro E.

• Dipartimento di Matematica, Politecnico di Milano, Milano, Italy

Bibliografia

• [1] Perrin D. Finite automata. Handbook of theoretical computer science, J. van Leewen (eds.) Elsevier, B. (1990) pp. 1-57.
• [2] 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, LNCS, vol. 5196, Springer, Berlin (2008) pp.11-27. doi:10.1007=978-3-540-88282-4_4.
• [3] Maslennikova M.I. Reset Complexity of Ideal Languages. In: M. Bieliková (eds.), SOFSEM 2012, Proc. Institute of Computer Science Academy of Sciences of the Czech Republic, vol. II (2012) pp. 33-44.
• [4] Gusev V.V, Maslennikova M.I, Pribavkina E.V. Principal Ideal languages and synchronizing automata. In: V.Halava, J.Karhumäki, Yu. Matiyasevich (eds.), the Special Issue of the RuFiDiM 2012, Fundamenta Informaticae, vol. 132(1) (2014) pp. 95-108. doi:10.3233=FI-2014-1034.
• [5] Reis R, Rodaro E. Regular ideal languages and synchronizing automata. In: J. Karhumäki, A. Lepistö, L. Zamboni (eds.), WORDS 2013, LNCS, vol. 8079, Springer, Heidelberg (2013) pp. 205-216. doi:10.1007=978-3-642-40579-2_22.
• [6] Maslennikova M. Complexity of checking whether two automata are synchronized by the same language. In: H.Jürgensen, J. Karhumäki, Al. Okhotin (eds.), DCFS 2014, LNCS, vol. 8614, Springer (2014) pp. 306-317. doi:10.1007=978-3-319-09704-6_27.
• [7] Maslennikova M. Reset complexity of ideal languages over a binary alphabet. In: G. Pighizzini, C. Câmpeanu (eds.), DCFS 2017, LNCS, vol. 10316, Springer (2017) pp. 262-273. doi:10.1007=978-3-319-60252-3_21.
• [8] Černý, J. Poznámka k homogénnym eksperimentom s konečnými automatami., Mat.-Fyz. Cas. Slovensk. Akad. Vied. 14 (1964) pp. 208-216.
• [9] Volkov M.V. Synchronizing automata preserving a chain of partial orders. Theor. Comp. Sci., vol. 410 (2009) pp. 3513-3519. doi: 10.1007=978-3-540-76336-9_5.
• [10] Gusev V.V, Maslennikova M.I, Pribavkina E.V. Finitely generated ideal languauges and synchronizing automata. In: J. Karhumäki, A. Lepisto, L. Zamboni (eds.), WORDS 2013, LNCS, vol. 8079, Springer (2013) pp. 143-153. doi:10.1007=978-3-642-40579-2_16.
• [11] Maslennikova M, Rodaro E. Representation of (left) ideal regular languages by synchronizing automata. In: L. Beklemishev, D. Musatov (eds.) 10th Int. Comp. Sci. Symp. CSR 2015, LNCS, vol. 9139, Springer-Verlag, Berlin-Heidelberg (2015) pp. 325-338. doi:10.1007=978-3-319-20297-6_21.
• [12] Pribavkina E, Rodaro E. Synchronizing automata with finitely many minimal synchronizing words. Information and Computation, vol. 209(3) (2011) pp. 568-579. doi: 10.1016=j.ic.2010.11.020.
• [13] Holzer M, König B. On deterministic finite automata and syntactic monoid size. Theoret. Comput. Sci. 327 (2004) pp. 319-347. doi:10.1016=j.tcs.2004.04.010.