Finitely generated ideal languages and synchronizing automata

2013/05/02 by Vladimir V. Gusev, Gusev, Vladimir V., Marina Maslennikova +4
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Algebra and Logic #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1305.0336

Submitted to WORDS 2013

arxiv created 2013/05/02 · openalex publication_date 2013/05/02 · arxiv updated 2013/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study representations of ideal languages by means of strongly connected synchronizing automata. For every finitely generated ideal language L we construct such an automaton with at most 2ⁿ states, where n is the maximal length of words in L. Our constructions are based on the De Bruijn graph.

Related

• Principal ideal languages and synchronizing automata
• Representation of (Left) Ideal Regular Languages by Synchronizing Automata
• Synchronizing automata and the language of minimal reset words
• Modifying the upper bound on the length of minimal synchronizing word
• A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group