Completely reachable automata

DOI10.1007/978-3-319-41114-9_1zbMATH Open1435.68145arXiv1607.00554OpenAlexW2468044850MaRDI QIDQ2829965FDOQ2829965

Authors: Eugenija Bondar, M. V. Volkov 

Publication date: 9 November 2016

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

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.

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

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

zbMATH Keywords

PSPACE-completenessdeterministic finite automatonsyntactic complexitytransition monoidcomplete reachability

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

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

Cited In (18)

• 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 of ideal languages over a binary alphabet
• Synchronization problems in automata without non-trivial cycles
• Reset complexity and completely reachable automata with simple idempotents
• On completely reachable automata and subset reachability
• Title not available (Why is that?)
• Title not available (Why is that?)
• Preimage problems for deterministic finite automata
• Sync-maximal permutation groups equal primitive permutation groups
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
• On the interplay between Černý and Babai's conjectures
• The length of subset reachability in nondeterministic automata
• Complexity of preimage problems for deterministic finite automata
• Binary completely reachable automata
• Completely distinguishable automata and the set of synchronizing words
• Reset thresholds of transformation monoids
• 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)