The word problem of \(\mathbb{Z}^n\) is a multiple context-free language

DOI10.1515/gcc-2018-0003zbMath1394.68213arXiv1702.02926OpenAlexW2593563509MaRDI QIDQ1647858

Meng-Che Ho

Publication date: 27 June 2018

Published in: Groups, Complexity, Cryptology (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1702.02926

zbMATH Keywords

abelian groupsword problemformal languagemultiple context-free language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Torsion-free groups, finite rank (20K15)

Related Items (7)

\(O_n\) is an \(n\)-MCFL ⋮ Self-avoiding walks and multiple context-free languages ⋮ Comparing consecutive letter counts in multiple context-free languages ⋮ 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
• Groups, the theory of ends, and context-free languages
• On multiple context-free grammars
• Groups whose word problems are not semilinear
• MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies
• ON GROUPS AND COUNTER AUTOMATA
• GROUPS THAT DO AND DO NOT HAVE GROWING CONTEXT-SENSITIVE WORD PROBLEM
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• Three models for the description of language

This page was built for publication: The word problem of \(\mathbb{Z}^n\) is a multiple context-free language