Finite-automaton aperiodicity is PSPACE-complete

DOI10.1016/0304-3975(91)90075-DzbMATH Open0733.68038MaRDI QIDQ809608FDOQ809608

Publication date: 1991

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

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

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

Cites Work

Title not available (Why is that?)
Relationships between nondeterministic and deterministic tape complexities
Complexity of some problems from the theory of automata
Nondeterministic Space is Closed under Complementation
Title not available (Why is that?)
Title not available (Why is that?)
On finite monoids having only trivial subgroups
The parallel complexity of finite-state automata problems

Cited In (36)

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

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)