Context-Freeness of Word-MIX Languages

DOI10.1007/978-3-030-48516-0_23MaRDI QIDQ5041269zbMATH OpenOpenAlexFDO

Authors Ryoma Sin'ya

Publication date 13 October 2022

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

Full work available at URL https://doi.org/10.1007/978-3-030-48516-0_23

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Context-freeness of the power of context-free languages is undecidable
• A context-free language decision problem
• scientific article; zbMATH DE number 1560303
• Context-Free Languages of Countable Words
• The context-freeness of the languages associated with vector addition systems is decidable

Cites work

• A pumping lemma for \textbf{DLI}-languages
• A sharpening of the Parikh mapping
• Absoluteness of subword inequality is undecidable
• Counting subwords and regular languages
• scientific article; zbMATH DE number 1259068 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies
• On Context-Free Languages
• Subword histories and Parikh matrices
• The context-freeness of the languages associated with vector addition systems is decidable
• The context-freeness problem is coNP-complete for flat counter systems
• Unambiguous constrained automata

Cited in

(2)

• Context-Free Languages of Countable Words
• scientific article; zbMATH DE number 176237 (Why is no real title available?)

This page was built for publication: Context-Freeness of Word-MIX Languages

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