Efficient algorithms for membership in Boolean hierarchies of regular languages

DOI10.1016/J.TCS.2016.07.017zbMATH Open1348.68103OpenAlexW1481654098MaRDI QIDQ306282FDOQ306282

Victor Selivanov, Christian Glaßer, H. Schmitz

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

Recommendations

• Efficient algorithms for membership in Boolean hierarchies of regular languages
• An efficient null-free procedure for deciding regular language membership
• Efficient Enumeration of Regular Languages
• Boolean algebras of regular languages
• Boolean Algebras of Regular Languages
• Compressed membership problems for regular expressions and hierarchical automata
• Efficient algorithms for morphisms over omega-regular languages
• Boolean circuit complexity of regular languages
• scientific article; zbMATH DE number 777280
• Efficient separability of regular languages by subsequences and suffixes

zbMATH Keywords

computational complexitydecidabilityefficient algorithmsautomata and formal languagesBoolean hierarchydot-depth hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• On the Computational Complexity of Algorithms
• 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?)
• On finite monoids having only trivial subgroups
• Classifying regular events in symbolic logic
• Weak Second‐Order Arithmetic and Finite Automata
• The difference and truth-table hierarchies for NP
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• 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
• Dot-depth of star-free events
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hierarchies and reducibilities on regular languages related to modulo counting
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Boolean Hierarchy I: Structural Properties
• Title not available (Why is that?)
• Title not available (Why is that?)
• THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS
• Title not available (Why is that?)
• Title not available (Why is that?)
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Mathematical Foundations of Computer Science 2004
• Finite-automaton aperiodicity is PSPACE-complete
• Languages polylog-time reducible to dot-depth 1/2

Cited In (4)

• On the main scientific achievements of Victor Selivanov
• Difference hierarchies and duality with an application to formal languages
• A Survey on Difference Hierarchies of Regular Languages
• Well-Quasi Orders and Hierarchy Theory

This page was built for publication: Efficient algorithms for membership in Boolean hierarchies of regular languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306282)