\(O_n\) is an \(n\)-MCFL

DOI10.1016/j.jcss.2022.02.003zbMath1483.68169arXiv2012.12100OpenAlexW4213278535MaRDI QIDQ2121469

Sylvain Salvati, Frédéric Meunier, Kilian Gebhardt

Publication date: 4 April 2022

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

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

zbMATH Keywords

formal languagesTucker lemmacommutative languagesmultiple context-free languagesnecklace-splitting theoremword problem in groups

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (1)

Groups whose word problems are accepted by abelian \(G\)-automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Groups, the theory of ends, and context-free languages
• On multiple context-free grammars
• The word problem of \(\mathbb{Z}^n\) is a multiple context-free language
• MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies
• Combinatorial necklace splitting
• A generalization of Tucker's combinatorial lemma with topological applications
• Algorithmic construction of sets for k -restrictions
• A Simple Proof of the Hobby-Rice Theorem
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• A Moment Problem in L 1 Approximation

This page was built for publication: \(O_n\) is an \(n\)-MCFL