Completely reachable automata

DOI10.1007/978-3-319-41114-9_1MaRDI QIDQ2829965zbMATH OpenOpenAlexFDO

Authors Eugenija Bondar, M. V. Volkov

Publication date 9 November 2016

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.00554

zbMATH Keywords

PSPACE-completenessdeterministic finite automatonsyntactic complexitytransition monoidcomplete reachability

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We present a few results and several open problems concerning complete deterministic finite automata in which every non-empty subset of the state set occurs as the image of the whole state set under the action of a suitable input word.

Recommendations

• A characterization of completely reachable automata
• Hardly reachable subsets and completely reachable automata with 1-deficient words
• On completely reachable automata and subset reachability
• On the completeness of systems of finite automata
• scientific article; zbMATH DE number 512840

Cites work

• scientific article; zbMATH DE number 3722702 (Why is no real title available?)
• scientific article; zbMATH DE number 6438650 (Why is no real title available?)
• Classical finite transformation semigroups. An introduction.
• Classification of \(\mathcal L\)-cross-sections of the finite symmetric semigroup up to isomorphism
• Complexity Analysis: Transformation Monoids of Finite Automata
• Equivalence of topological Markov shifts
• Primitive digraphs with large exponents and slowly synchronizing automata
• RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
• Synchronizing Automata and the Černý Conjecture
• Syntactic complexity of \(\mathcal{R}\)- and \(\mathcal{J}\)-trivial regular languages
• The road coloring problem
• Upper bound on syntactic complexity of suffix-free languages

Cited in

(17)

• scientific article; zbMATH DE number 7770050 (Why is no real title available?)
• 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
• The length of subset reachability in nondeterministic automata
• Reset thresholds of transformation monoids
• Binary completely reachable automata
• On the interplay between Černý and Babai's conjectures
• On completely reachable automata and subset reachability
• Reset complexity and completely reachable automata with simple idempotents
• scientific article; zbMATH DE number 7644292 (Why is no real title available?)
• Complexity of preimage problems for deterministic finite automata
• Completely distinguishable automata and the set of synchronizing words
• Preimage problems for deterministic finite automata
• Reset complexity of ideal languages over a binary alphabet
• Sync-maximal permutation groups equal primitive permutation groups
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
• A characterization of completely reachable automata

This page was built for publication: Completely reachable automata

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