MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies

DOI10.1016/j.jcss.2015.03.004zbMath1325.68133OpenAlexW2020797398MaRDI QIDQ2353402

Sylvain Salvati

Publication date: 13 July 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2015.03.004

zbMATH Keywords

algebraic topologyJordan curvesformal language theorygroup languagesmildly context-sensitive languageshigher-order collapsible pushdown automataIO and OI hierarchies

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (10)

\(O_n\) is an \(n\)-MCFL ⋮ Self-avoiding walks and multiple context-free languages ⋮ Context-Freeness of Word-MIX Languages ⋮ Comparing consecutive letter counts in multiple context-free languages ⋮ The word problem of \(\mathbb{Z}^n\) is a multiple context-free language ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Closure properties in the class of multiple context-free groups ⋮ Groups whose word problems are not semilinear ⋮ IDL-PMCFG, a grammar formalism for describing free word order languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Groups, the theory of ends, and context-free languages
• Cônes rationnels commutatifs
• The IO- and OI-hierarchies
• On multiple context-free grammars
• Theorems and counterexamples in mathematics
• Transductions des langages de Chomsky
• On the expressive power of abstract categorial grammars: Representing context-free formalisms
• The failure of the strong pumping lemma for multiple context-free languages
• AFL with the semilinear property
• THE WORD PROBLEM
• The Copying Power of Well-Nested Multiple Context-Free Grammars
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• An automata-theoretical characterization of the OI-hierarchy
• Real-time solutions of the origin-crossing problem
• Studies in abstract families of languages
• Foundations of Software Science and Computational Structures
• A remark on method in transfinite algebra

This page was built for publication: MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies