Checking Whether an Automaton Is Monotonic Is NP-complete

DOI10.1007/978-3-319-22360-5_23zbMath1465.68166arXiv1407.5068OpenAlexW1203745828MaRDI QIDQ2947429

Marek Szykuła

Publication date: 23 September 2015

Published in: Implementation and Application of Automata (Search for Journal in Brave)

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

zbMATH Keywords

complexityNP-completenesspartial orderorder-preservingtransition semigrouplinear ordercyclic ordermonotonic automatonoriented automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Constrained synchronization for monotonic and solvable automata and automata with simple idempotents

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decision problems for convex languages
• Descriptional and computational complexity of finite automata -- a survey
• Finite-automaton aperiodicity is PSPACE-complete
• Synchronizing automata preserving a chain of partial orders
• On the ranks of certain semigroups of order-preserving transformations
• The dot-depth hierarchy of star-free languages is infinite
• Approximating the minimum length of synchronizing words is hard
• Synchronizing generalized monotonic automata
• Computing the shortest reset words of synchronizing automata
• On Nonpermutational Transformation Semigroups with an Application to Syntactic Complexity
• Synchronizing Automata with Extremal Properties
• Approximating Minimum Reset Sequences
• Large Aperiodic Semigroups
• Reset Sequences for Monotonic Automata
• The Complexity of Finding Reset Words in Finite Automata
• Experimental Study of the Shortest Reset Word of Random Automata
• Generating Small Automata and the Černý Conjecture
• A polynomial time algorithm for the local testability problem of deterministic finite automata
• The complexity of satisfiability problems