Checking Whether an Automaton Is Monotonic Is NP-complete
From MaRDI portal
Publication:2947429
DOI10.1007/978-3-319-22360-5_23zbMath1465.68166arXiv1407.5068OpenAlexW1203745828MaRDI QIDQ2947429
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
complexityNP-completenesspartial orderorder-preservingtransition semigrouplinear ordercyclic ordermonotonic automatonoriented automaton
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
