scientific article; zbMATH DE number 1346363

MaRDI QIDQ4266486zbMATH OpenFDO

Authors Alexandru Mateescu, Arto Salomaa

Publication date 24 October 1999

zbMATH Keywords

finite automataroad coloring problemSheffer functionstruth functions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The Černý conjecture for automata respecting intervals of a directed graph
• scientific article; zbMATH DE number 1206597
• Synchronised automata
• The Černý conjecture for one-cluster automata with prime length cycle
• The Černý conjecture for automata with blocking states

Cited in

(27)

• Synchronizing finite automata on Eulerian digraphs.
• The size of power automata.
• Synchronizing generalized monotonic automata
• Composition sequences for functions over a finite domain.
• An algorithm for road coloring
• A multi-parameter analysis of hard problems on deterministic finite automata
• Slowly synchronizing automata with zero and noncomplete sets
• Compositions over a finite domain: From completeness to synchronizable automata
• Composition sequences and synchronizing automata
• Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete
• The Synchronization Problem for Locally Strongly Transitive Automata
• Synchronizing Automata Preserving a Chain of Partial Orders
• The Synchronization Problem for Strongly Transitive Automata
• Synchronizing Automata and the Černý Conjecture
• 2-Synchronizing Words
• Finitely Generated Synchronizing Automata
• Synchronizing random automata on a 4-letter alphabet
• The length of subset reachability in nondeterministic automata
• On randomized generation of slowly synchronizing automata
• A linear bound on the \(k\)-rendezvous time for primitive sets of NZ matrices
• Synchronizing automata with finitely many minimal synchronizing words
• The Synchronizing Probability Function for Primitive Sets of Matrices
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
• Synchronizing monotonic automata
• The road coloring problem
• Synchronizing automata preserving a chain of partial orders
• Synchronizing automata with a letter of deficiency 2

This page was built for publication:

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