The Dot-Depth Hierarchy, 45 Years Later

DOI10.1142/9789813148208_0008zbMath1404.68073OpenAlexW4205551952MaRDI QIDQ4683189

Jean-Eric Pin

Publication date: 20 September 2018

Published in: The Role of Theory in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/9789813148208_0008

zbMATH Keywords

complexity classesaperiodic monoidstar-free languageconcatenation hierarchypositive varietysyntactic orderBrzozowski hierarchyordered syntactic monoid

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items (15)

A Survey on Difference Hierarchies of Regular Languages ⋮ Measuring power of locally testable languages ⋮ Concatenation hierarchies: new bottle, old wine ⋮ A Trichotomy for Regular Trail Queries ⋮ Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups ⋮ Separating Without Any Ambiguity. ⋮ Subsequence versus substring constraints in sequence pattern languages ⋮ Pro-aperiodic monoids via saturated models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Separating regular languages with two quantifier alternations ⋮ The Complexity of Separation for Levels in Concatenation Hierarchies ⋮ On All Things Star-Free ⋮ Varieties ⋮ State complexity of permutation and related decision problems on alphabetical pattern constraints

This page was built for publication: The Dot-Depth Hierarchy, 45 Years Later