Generic results for concatenation hierarchies

DOI10.1007/s00224-018-9867-0zbMath1423.68264arXiv1710.04313OpenAlexW2963440540MaRDI QIDQ2311891

Thomas Place, Marc Zeitoun

Publication date: 4 July 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

first-order logicmembership problemregular languagesseparation problemconcatenation hierarchiesquantifier alternation

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 (8)

Pointlike sets and separation: a personal perspective ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ How many times do you need to go back to the future in unary temporal logic? ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ The Complexity of Separation for Levels in Concatenation Hierarchies ⋮ Unnamed Item ⋮ Characterizing level one in group-based concatenation hierarchies ⋮ State complexity of permutation and related decision problems on alphabetical pattern constraints

Cites Work

• Factorization forests for infinite words and applications to countable scattered linear orderings
• Factorization forests of finite height
• Representation theorems on regular languages
• 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
• Concatenation hierarchies: new bottle, old wine
• Languages of dot-depth 3/2
• Transition graphs and the star-height of regular events
• Dot-depth of star-free events
• Automata Studies. (AM-34)
• Linear Automaton Transformations
• An application of the Ehrenfeucht-Fraisse game in formal language theory
• The Height of Factorization Forests
• Equations Defining the Polynomial Closure of a Lattice of Regular Languages
• Separating regular languages with two quantifier alternations
• Separating Regular Languages with Two Quantifiers Alternations
• Star Height via Games
• Polynomial closure and unambiguous product
• Open Problems About Regular Languages, 35 Years Later
• THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS
• Adding Successor
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• The Power of Diversity
• 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
• A delay theorem for pointlikes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Generic results for concatenation hierarchies