A counterexample to a conjecture concerning concatenation hierarchies

DOI10.1016/J.IPL.2009.09.011MaRDI QIDQ990089zbMATHOpenAlexWikidataFDO

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

zbMATH Keywords

formal languagesregular languagesstar-free languagesconcatenation hierarchieslevel two

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

• scientific article; zbMATH DE number 3961008 (Why is no real title available?)
• scientific article; zbMATH DE number 4034007 (Why is no real title available?)
• scientific article; zbMATH DE number 1254093 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 798167 (Why is no real title available?)
• A Reiterman theorem for pseudovarieties of finite first-order structures
• A conjecture on the concatenation product
• INVERSE MONOIDS OF DOT-DEPTH TWO
• On a conjecture concerning dot-depth two languages
• On the extension problem for partial permutations
• Polynomial closure and unambiguous product
• Profinite semigroups, Mal'cev products, and identities
• Semigroups and languages of dot-depth two
• The Birkhoff theorem for finite algebras

Cited in

(2)

• scientific article; zbMATH DE number 3894493 (Why is no real title available?)
• New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages

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)