Synchronizing automata preserving a chain of partial orders

DOI10.1016/j.tcs.2009.03.021zbMath1194.68148OpenAlexW2009589430MaRDI QIDQ840772

Mikhail V. Volkov

Publication date: 14 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10995/72269

zbMATH Keywords

synchronizing automataaperiodic automataweakly monotonic automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (24)

Computational complexity of synchronization under sparse regular constraints ⋮ Strongly connected synchronizing automata and the language of minimal reset words ⋮ The Černý conjecture and 1-contracting automata ⋮ Unnamed Item ⋮ Ideal regular languages and strongly connected synchronizing automata ⋮ Representation of (Left) Ideal Regular Languages by Synchronizing Automata ⋮ Primitive digraphs with large exponents and slowly synchronizing automata ⋮ Checking Whether an Automaton Is Monotonic Is NP-complete ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Complexity of road coloring with prescribed reset words ⋮ Slowly synchronizing automata with zero and noncomplete sets ⋮ Complexity of problems concerning reset words for cyclic and Eulerian automata ⋮ Preimage problems for deterministic finite automata ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices ⋮ A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number ⋮ Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata ⋮ Semisimple Synchronizing Automata and the Wedderburn-Artin Theory ⋮ Extremal synchronizing circular automata ⋮ An Extremal Series of Eulerian Synchronizing Automata ⋮ LOWER BOUNDS FOR THE LENGTH OF RESET WORDS IN EULERIAN AUTOMATA ⋮ Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata ⋮ Sync-maximal permutation groups equal primitive permutation groups ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orienting polygonal parts without sensors
• An extremal problem for two families of sets
• Reset words for commutative and solvable automata
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing generalized monotonic automata
• Composition sequences for functions over a finite domain.
• Model-based testing of reactive systems. Advanced lectures.
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• On two Combinatorial Problems Arising from Automata Theory
• RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
• Developments in Language Theory

This page was built for publication: Synchronizing automata preserving a chain of partial orders