We follow language theoretic approach to synchronizing automata and Cerny'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.

Trim strongly connected synchronizing automata and ideal languages

Rodaro, Emanuele
2018-01-01

Abstract

We follow language theoretic approach to synchronizing automata and Cerny'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.
2018
Ideal language; Reset complexity; Reset left regular decomposition; Reset word; Strongly connected automaton.; Synchronizing automaton; Theoretical Computer Science; Algebra and Number Theory; Information Systems; Computational Theory and Mathematics
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1078156
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact