Polynomial operations and hierarchies of concatenation

DOI10.1016/0304-3975(91)90268-7zbMath0751.68031OpenAlexW2222913098MaRDI QIDQ1183588

Mustapha Arfi

Publication date: 28 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90268-7

zbMATH Keywords

concatenationStraubing hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (20)

Some complexity results for polynomial rational expressions. ⋮ Polynomial closure and unambiguous product ⋮ Polynomial closure and unambiguous product ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ Concatenation hierarchies: new bottle, old wine ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ Perfect correspondences between dot-depth and polynomial-time hierarchies ⋮ Separating Without Any Ambiguity. ⋮ Theme and Variations on the Concatenation Product ⋮ Languages of dot-depth 3/2 ⋮ On Shuffle Ideals ⋮ The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin ⋮ Local testability from words to traces, a suitable definition ⋮ Logic, semigroups and automata on words ⋮ Generic results for concatenation hierarchies ⋮ One quantifier alternation in first-order logic with modular predicates ⋮ Geometrically closed positive varieties of languages ⋮ Algebraic tools for the concatenation product. ⋮ A conjecture on the concatenation product ⋮ Unresolved systems of language equations: expressive power and decision problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limitedness theorem on finite automata with distance functions
• Representation theorems on regular languages
• First-order logic and star-free sets
• Semigroups and languages of dot-depth two
• Algorithms for determining relative star height and star height
• Inverse monoids of dot-depth two
• Classifying regular events in symbolic logic
• Sur le produit de concatenation non ambigu
• Aperiodic homomorphisms and the concatenation product of recognizable sets
• Finite semigroup varieties of the form V*D
• Regular languages of star height one

This page was built for publication: Polynomial operations and hierarchies of concatenation