Finite-automaton aperiodicity is PSPACE-complete
From MaRDI portal
Publication:809608
DOI10.1016/0304-3975(91)90075-DzbMath0733.68038MaRDI QIDQ809608
Publication date: 1991
Published in: Theoretical Computer Science (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (33)
On Boolean combinations forming piecewise testable languages ⋮ On the expressive power of temporal logic ⋮ Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words ⋮ Complexity Analysis: Transformation Monoids of Finite Automata ⋮ On the Complexity of k-Piecewise Testability and the Depth of Automata ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Problems on finite automata and the exponential time hypothesis ⋮ The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete ⋮ The intersection problem for finite monoids ⋮ Checking Whether an Automaton Is Monotonic Is NP-complete ⋮ Unnamed Item ⋮ Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic ⋮ Forbidden Patterns for FO2 Alternation Over Finite and Infinite Words ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Unnamed Item ⋮ Deciding FO-definability of regular languages ⋮ Aperiodicity in Tree Automata ⋮ PSPACE-completeness of certain algorithmic problems on the subgroups of free groups ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Theme and Variations on the Concatenation Product ⋮ Two-letter group codes that preserve aperiodicity of inverse finite automata. ⋮ QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Expressive power of existential first-order sentences of Büchi's sequential calculus ⋮ Complexity of deciding detectability in discrete event systems ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ The complexity of properties of transformation semigroups ⋮ Logic, semigroups and automata on words ⋮ The Complexity of Separation for Levels in Concatenation Hierarchies ⋮ On verification of D-detectability for discrete event systems ⋮ Problems on Finite Automata and the Exponential Time Hypothesis ⋮ Varieties ⋮ \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The parallel complexity of finite-state automata problems
- Relationships between nondeterministic and deterministic tape complexities
- Complexity of some problems from the theory of automata
- Nondeterministic Space is Closed under Complementation
- On finite monoids having only trivial subgroups
This page was built for publication: Finite-automaton aperiodicity is PSPACE-complete
