Concatenation hierarchies: new bottle, old wine

DOI10.1007/978-3-319-58747-9_5zbMath1489.68134OpenAlexW2610605453MaRDI QIDQ2399361

Thomas Place, Marc Zeitoun

Publication date: 22 August 2017

Full work available at URL: https://doi.org/10.1007/978-3-319-58747-9_5

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Research exposition (monographs, survey articles) pertaining to computer science (68-02) History of computer science (68-03)

Related Items (6)

A Survey on Difference Hierarchies of Regular Languages ⋮ Unboundedness Problems for Languages of Vector Addition Systems. ⋮ Unnamed Item ⋮ Separating regular languages with two quantifier alternations ⋮ Generic results for concatenation hierarchies ⋮ The Quantifier Alternation Hierarchy of Synchronous Relations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-order logic and star-free sets
• Algorithms for determining relative star height and star height
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• Polynomial operations and hierarchies of concatenation
• The dot-depth hierarchy of star-free languages is infinite
• Polynomial closure and unambiguous product
• Finite semigroup varieties of the form V*D
• Languages of dot-depth 3/2
• Transition graphs and the star-height of regular events
• Classification of noncounting events
• Separating Regular Languages with Two Quantifiers Alternations
• Star Height via Games
• Open Problems About Regular Languages, 35 Years Later
• The Dot-Depth Hierarchy, 45 Years Later
• THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• An Explicit Formula for the Intersection of Two Polynomials of Regular Languages
• Distance desert automata and the star height problem
• On finite monoids having only trivial subgroups
• On a question of Eggan

This page was built for publication: Concatenation hierarchies: new bottle, old wine