Efficient algorithms for membership in Boolean hierarchies of regular languages
From MaRDI portal
Publication:306282
DOI10.1016/j.tcs.2016.07.017zbMath1348.68103OpenAlexW1481654098MaRDI QIDQ306282
Christian Glaßer, Heinz Schmitz, Victor L. Selivanov
Publication date: 31 August 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.07.017
computational complexitydecidabilityBoolean hierarchyefficient algorithmsautomata and formal languagesdot-depth hierarchy
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (4)
A Survey on Difference Hierarchies of Regular Languages ⋮ On the main scientific achievements of Victor Selivanov ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ Difference hierarchies and duality with an application to formal languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finite-automaton aperiodicity is PSPACE-complete
- Languages polylog-time reducible to dot-depth 1/2
- Characterizations of some classes of regular events
- First-order logic and star-free sets
- Semigroups and languages of dot-depth two
- A generalization of the Schützenberger product of finite monoids
- Classification of finite monoids: the language approach
- Classifying regular events in symbolic logic
- Regular languages in \(NC\)
- Polynomial closure and unambiguous product
- Programs over semigroups of dot-depth one
- Logic, semigroups and automata on words
- Finite semigroup varieties of the form V*D
- On the expressive power of temporal logic
- Languages of dot-depth 3/2
- Relationships between nondeterministic and deterministic tape complexities
- Dot-depth of star-free events
- Weak Second‐Order Arithmetic and Finite Automata
- Hierarchies and reducibilities on regular languages related to modulo counting
- Complexity of some problems from the theory of automata
- The difference and truth-table hierarchies for NP
- Nondeterministic Space is Closed under Complementation
- The Boolean Hierarchy I: Structural Properties
- THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS
- Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
- Mathematical Foundations of Computer Science 2004
- On finite monoids having only trivial subgroups
- On the Computational Complexity of Algorithms
This page was built for publication: Efficient algorithms for membership in Boolean hierarchies of regular languages
