A strengthening of the MCFL-ness of $O_2$

Abstract:In the last years, a number of proofs of the fact that $O_2$ is a multiple context-free grammar (MCFG) were given. Such results can be exploited in the fields of both computational linguistics and of computational algebra. Here, we focus on a recent such proof spelled in terms of factorizations of string tuples, and give a new result with a stronger characterization of such factorizations than in existing theorems.

Formal Languages and Automata Theory (cs.FL); Artificial Intelligence (cs.AI); Logic in Computer Science (cs.LO); Logic (math.LO)

arXiv:2608.18813 [cs.FL]

(or arXiv:2608.18813v1 [cs.FL] for this version)

https://doi.org/10.48550/arXiv.2608.18813 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.