MIX is a 2-MCFL and the word problem in Z^2 is captured by the IO and the OI hierarchies

DOI10.1016/J.JCSS.2015.03.004MaRDI QIDQ2353402zbMATH OpenOpenAlexFDO

Authors S. 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 topologyformal language theorygroup languageshigher-order collapsible pushdown automataIO and OI hierarchiesJordan curvesmildly context-sensitive languages

Mathematics Subject Classification ID

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

Review text

Different presentations of the same group define different group languages that can be translated into each other by rational transductions. A general question consists in relating algebraic properties of finitely presented and finitely generated groups with language-theoretic properties of their group languages. Such a question can be partially answered by characterizing the groups whose group-languages belong to a certain class of languages that is closed under rational transduction. The groups whose group languages are regular languages are finite groups and those whose group languages are context-free languages are virtually free groups [\textit{D. E. Muller} and \textit{P. E. Schupp}, J. Comput. Syst. Sci. 26, 295--310 (1983; Zbl 0537.20011)]. The group language of a simple presentation of \(\mathbb{Z}^2\) is the 2-dimensional origin-crossing language \(O_2=\{w \in \{a,\bar{a},b,\bar{b}\}^* \mid | w|_{a}=| w|_{\bar{a}}\land | w|_{b}=| w|_{\bar{b}}\}\), which is not context-free. An open problem in computational group theory is whether \(O_2\) is an indexed language. In this paper, the author shows that the problems whether MIX \(=\{w \in \{a,b,c\}^* \mid | w|_{a}= | w|_{b}=| w|_{c}\}\) and \(O_2\) are indexed languages are in fact equivalent, and he proves that MIX and \(O_2\) are 2-multiple context-free languages (MCFL). As 2-MCFLs form a class of languages that is included in both the IO and OI hierarchies, and as \(O_2\) is the group language of a simple presentation of \(\mathbb{Z}^2\), this gives a non-virtually-free group language (i.e. non-context-free group language) that is captured by the IO and OI hierarchies. Furthermore, the author proves MIX is not a mildly context-sensitive language.

Recommendations

• The word problem of \(\mathbb{Z}^n\) is a multiple context-free language
• \(O_n\) is an \(n\)-MCFL
• Groups with poly-context-free word problem.
• Context-free irreducible word problems in groups.
• Groups whose word problems are not semilinear

Cites work

• A remark on method in transfinite algebra
• AFL with the semilinear property
• An automata-theoretical characterization of the OI-hierarchy
• Cônes rationnels commutatifs
• Foundations of Software Science and Computational Structures
• Groups, the theory of ends, and context-free languages
• scientific article; zbMATH DE number 5560346 (Why is no real title available?)
• scientific article; zbMATH DE number 2087432 (Why is no real title available?)
• scientific article; zbMATH DE number 3235051 (Why is no real title available?)
• scientific article; zbMATH DE number 3312693 (Why is no real title available?)
• On multiple context-free grammars
• On the expressive power of abstract categorial grammars: Representing context-free formalisms
• Real-time solutions of the origin-crossing problem
• Studies in abstract families of languages
• The copying power of well-nested multiple context-free grammars
• The failure of the strong pumping lemma for multiple context-free languages
• The IO- and OI-hierarchies
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• THE WORD PROBLEM
• Theorems and counterexamples in mathematics
• Transductions des langages de Chomsky

Cited in

(14)

• The word problem of \(\mathbb{Z}^n\) is a multiple context-free language
• IDL-PMCFG, a grammar formalism for describing free word order languages
• \(O_n\) is an \(n\)-MCFL
• Closure properties in the class of multiple context-free groups
• Groups whose word problems are not semilinear
• scientific article; zbMATH DE number 7456062 (Why is no real title available?)
• Context-Freeness of Word-MIX Languages
• On the expressivity of linear recursion schemes
• Self-avoiding walks and multiple context-free languages
• Probabilistic verification beyond context-freeness
• Proof-theoretic aspects of the logic of scope
• Commutative semigroups with a context-free word problem
• O₂ is a multiple context-free grammar: an implementation-, formalisation-friendly proof
• Comparing consecutive letter counts in multiple context-free languages

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

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