Pages that link to "Item:Q809608"

The following pages link to Finite-automaton aperiodicity is PSPACE-complete (Q809608):

Displaying 36 items.

• Efficient algorithms for membership in Boolean hierarchies of regular languages (Q306282) (← links)
• Descriptional and computational complexity of finite automata -- a survey (Q553312) (← links)
• Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words (Q832937) (← links)
• Fine hierarchies and m-reducibilities in theoretical computer science (Q949621) (← links)
• \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata (Q1575552) (← links)
• Problems on finite automata and the exponential time hypothesis (Q1662614) (← links)
• Separability by piecewise testable languages is \textsc{PTime}-complete (Q1698734) (← links)
• Expressive power of existential first-order sentences of Büchi's sequential calculus (Q1772275) (← links)
• Complexity of deciding detectability in discrete event systems (Q1797011) (← links)
• Logic, semigroups and automata on words (Q1817074) (← links)
• On verification of D-detectability for discrete event systems (Q2065231) (← links)
• Varieties (Q2074217) (← links)
• On Boolean combinations forming piecewise testable languages (Q2358689) (← links)
• On the expressive power of temporal logic (Q2366686) (← links)
• The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete (Q2409237) (← links)
• Two-letter group codes that preserve aperiodicity of inverse finite automata. (Q2480773) (← links)
• Deciding FO-definability of regular languages (Q2695357) (← links)
• Regular expression star-freeness is PSPACE-complete (Q2763598) (← links)
• Problems on Finite Automata and the Exponential Time Hypothesis (Q2830210) (← links)
• Checking Whether an Automaton Is Monotonic Is NP-complete (Q2947429) (← links)
• Theme and Variations on the Concatenation Product (Q3014930) (← links)
• The intersection problem for finite monoids (Q3304129) (← links)
• Complexity Analysis: Transformation Monoids of Finite Automata (Q3451097) (← links)
• On the Complexity of k-Piecewise Testability and the Depth of Automata (Q3451116) (← links)
• Aperiodicity in Tree Automata (Q3522867) (← links)
• Descriptional and Computational Complexity of Finite Automata (Q3618565) (← links)
• PSPACE-completeness of certain algorithmic problems on the subgroups of free groups (Q4632433) (← links)
• (Q4636560) (← links)
• QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES (Q4923279) (← links)
• The complexity of properties of transformation semigroups (Q4960463) (← links)
• (Q4989409) (← links)
• (Q5005165) (← links)
• The Complexity of Separation for Levels in Concatenation Hierarchies (Q5090988) (← links)
• Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic (Q6135954) (← links)
• Forbidden Patterns for FO² Alternation Over Finite and Infinite Words (Q6169964) (← links)
• Decision problems for subregular classes (Q6666796) (← links)