Reset complexity of ideal languages over a binary alphabet

DOI10.1142/S0129054119400343MaRDI QIDQ5205048zbMATH OpenOpenAlexFDO

Authors Marina Maslennikova

Publication date 10 December 2019

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054119400343

zbMATH Keywords

PSPACE-completenessreset wordstate complexitysynchronizing automatonideal languagereset complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Complexity of checking whether two automata are synchronized by the same language
• Representation of (left) ideal regular languages by synchronizing automata
• Strongly connected synchronizing automata and the language of minimal reset words
• Ideal regular languages and strongly connected synchronizing automata
• The complexity of finding reset words in finite automata

Cites work

• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1142311 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• Completely reachable automata
• Complexity of checking whether two automata are synchronized by the same language
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• Reset complexity of ideal languages over a binary alphabet
• Slowly synchronizing automata and digraphs
• Synchronizing Automata and the Černý Conjecture
• Synchronizing Automata with Extremal Properties
• The Černý conjecture and 1-contracting automata

Cited in

(8)

• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• State complexity of the set of synchronizing words for circular automata and automata over binary alphabets
• Reset complexity and completely reachable automata with simple idempotents
• Sync-maximal permutation groups equal primitive permutation groups
• Binary and circular automata having maximal state complexity for the set of synchronizing words
• New characterizations of primitive permutation groups with applications to synchronizing automata
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
• Completely distinguishable automata and the set of synchronizing words

This page was built for publication: Reset complexity of ideal languages over a binary alphabet

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205048)