Reset complexity of ideal languages over a binary alphabet
From MaRDI portal
Publication:5205048
DOI10.1142/S0129054119400343zbMATH Open1427.68150OpenAlexW2621293383MaRDI QIDQ5205048FDOQ5205048
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
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
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Synchronizing Automata and the Černý Conjecture
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Černý conjecture and 1-contracting automata
- Title not available (Why is that?)
- Slowly synchronizing automata and digraphs
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- Synchronizing Automata with Extremal Properties
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Complexity of checking whether two automata are synchronized by the same language
- Reset complexity of ideal languages over a binary alphabet
- Completely reachable 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)
