A Survey on Difference Hierarchies of Regular Languages

DOI10.23638/LMCS-14(1:24)2018zbMath1390.68447arXiv1702.08023OpenAlexW4394829417MaRDI QIDQ4637687

Dominique Perrin, Olivier Carton, Jean-Eric Pin

Publication date: 25 April 2018

Full work available at URL: https://arxiv.org/abs/1702.08023

zbMATH Keywords

regular languagedifference hierarchysyntactic monoid

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Efficient algorithms for membership in Boolean hierarchies of regular languages
• Chain automata
• Concatenation hierarchies: new bottle, old wine
• Separating Regular Languages with First-Order Logic
• The difference and truth-table hierarchies for NP
• The Boolean Hierarchy I: Structural Properties
• On ω-regular sets
• A Conjecture on the Hall Topology for the Free Group
• A hierarchy of cyclic languages
• Chains and Superchains for ω-Rational Sets, Automata and Semigroups
• THE WAGNER HIERARCHY
• The Wadge-Wagner hierarchy of ω-rational sets
• Cyclic languages and strongly cyclic languages
• Polynomial closure of group languages and open sets of the Hall topology
• PROFINITE TOPOLOGIES IN FREE PRODUCTS OF GROUPS
• The Dot-Depth Hierarchy, 45 Years Later
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A Survey on Difference Hierarchies of Regular Languages