A counterexample to a conjecture concerning concatenation hierarchies

DOI10.1016/J.IPL.2009.09.011zbMATH Open1206.68165OpenAlexW2042514722WikidataQ122932637 ScholiaQ122932637MaRDI QIDQ990089FDOQ990089

Authors: Jorge Almeida, Ondřej Klíma 

Publication date: 2 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.09.011

Recommendations

• New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages
• On a conjecture concerning dot-depth two languages
• The dot-depth hierarchy, 45 years later
• scientific article; zbMATH DE number 3894493
• scientific article; zbMATH DE number 1223722

zbMATH Keywords

formal languagesregular languagesstar-free languagesconcatenation hierarchieslevel two

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Semigroups and languages of dot-depth two
• Polynomial closure and unambiguous product
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Birkhoff theorem for finite algebras
• On the extension problem for partial permutations
• On a conjecture concerning dot-depth two languages
• Title not available (Why is that?)
• Profinite semigroups, Mal'cev products, and identities
• A Reiterman theorem for pseudovarieties of finite first-order structures
• A conjecture on the concatenation product
• Title not available (Why is that?)
• INVERSE MONOIDS OF DOT-DEPTH TWO

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: A counterexample to a conjecture concerning concatenation hierarchies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990089)