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