On Decidability of Intermediate Levels of Concatenation Hierarchies

DOI10.1007/978-3-319-21500-6_4zbMath1434.68224OpenAlexW1161996442MaRDI QIDQ3451089

Michal Kunc, Jana Bartoňová, Ondřej Klíma, Jorge Almeida

Publication date: 10 November 2015

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://repositorio-aberto.up.pt/handle/10216/107467

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25)

Related Items (6)

Unnamed Item ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ Separating Without Any Ambiguity. ⋮ The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages ⋮ Complexity of universality and related problems for partially ordered NFAs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Locally trivial categories and unambiguous concatenation
• The Birkhoff theorem for finite algebras
• Classifying regular events in symbolic logic
• Polynomial closure and unambiguous product
• Profinite semigroups, Mal'cev products, and identities
• Finite semigroup varieties of the form V*D
• Dot-depth of star-free events
• Equations Defining the Polynomial Closure of a Lattice of Regular Languages
• Separating Regular Languages with Two Quantifiers Alternations
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• On finite monoids having only trivial subgroups

This page was built for publication: On Decidability of Intermediate Levels of Concatenation Hierarchies