Efficient algorithms for membership in Boolean hierarchies of regular languages

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

zbMATH Keywords

computational complexitydecidabilityBoolean hierarchyefficient algorithmsautomata and formal languagesdot-depth hierarchy

Mathematics Subject Classification ID

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