A Topological proof that O₂ is 2-MCFL

2017/10/12 by Subhadip Chowdhury, Chowdhury, Subhadip
Computer Science · Mathematics · #Algebraic Topology (math.AT) #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Topological and Geometric Data Analysis #cs.FL #math.AT #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1710.04597

11 figures, 2 tables

openalex publication_date 2017/10/12 · arxiv created 2017/10/31 · arxiv updated 2017/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a new proof of Salvati's theorem that the group language O₂ is 2 multiple context free. Unlike Salvati's proof, our arguments do not use any idea specific to two-dimensions. This raises the possibility that the argument might generalize to O_n.

Related

• A short proof that O₂ is an MCFL
• O_n is an n-MCFL
• The Word Problem of ℤⁿ Is a Multiple Context-Free Language
• O₂ is a multiple context-free grammar: an implementation-, formalisation-friendly proof
• Topology and Strings: Topics in N=2