Finite-automaton aperiodicity is PSPACE-complete

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

scientific article; zbMATH DE number 1134629
Regular expression star-freeness is PSPACE-complete
scientific article; zbMATH DE number 1254105
Complexity of some problems from the theory of automata
THE DOT-DEPTH OF A GENERATING CLASS OF APERIODIC MONOIDS IS COMPUTABLE

Cites work

scientific article; zbMATH DE number 3664335 (Why is no real title available?)
scientific article; zbMATH DE number 3495598 (Why is no real title available?)
scientific article; zbMATH DE number 3032896 (Why is no real title available?)
Complexity of some problems from the theory of automata
Nondeterministic Space is Closed under Complementation
On finite monoids having only trivial subgroups
Relationships between nondeterministic and deterministic tape complexities
The parallel complexity of finite-state automata problems

Cited in

(36)

Two-letter group codes that preserve aperiodicity of inverse finite automata.
Complexity of deciding detectability in discrete event systems
Descriptional and computational complexity of finite automata -- a survey
The Complexity of Separation for Levels in Concatenation Hierarchies
On verification of D-detectability for discrete event systems
PSPACE-completeness of certain algorithmic problems on the subgroups of free groups
QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
The intersection problem for finite monoids
Testing Simon's congruence
Regular expression star-freeness is PSPACE-complete
Problems on finite automata and the exponential time hypothesis
On the expressive power of temporal logic
Problems on finite automata and the exponential time hypothesis
Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words
Separability by piecewise testable languages is \textsc{PTime}-complete
On Boolean combinations forming piecewise testable languages
Theme and variations on the concatenation product
On the complexity of \(k\)-piecewise testability and the depth of automata
Descriptional and Computational Complexity of Finite Automata
Deciding FO-definability of regular languages
Checking whether an automaton is monotonic is NP-complete
scientific article; zbMATH DE number 6862041 (Why is no real title available?)
scientific article; zbMATH DE number 7350780 (Why is no real title available?)
Varieties
Efficient algorithms for membership in Boolean hierarchies of regular languages
Logic, semigroups and automata on words
The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete
The complexity of properties of transformation semigroups
Expressive power of existential first-order sentences of Büchi's sequential calculus
Forbidden Patterns for FO² Alternation Over Finite and Infinite Words
Complexity Analysis: Transformation Monoids of Finite Automata
\texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
Fine hierarchies and m-reducibilities in theoretical computer science
Decision problems for subregular classes
Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
Aperiodicity in Tree Automata

This page was built for publication: Finite-automaton aperiodicity is PSPACE-complete

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