Parallel Hyperedge Replacement String Languages

Graham Campbell
(School of Mathematics, Statistics and Physics, Newcastle University, Newcastle upon Tyne, United Kingdom)

There are many open questions surrounding the characterisation of groups with context-sensitive word problem. Only in 2018 was it shown that all finitely generated virtually Abelian groups have multiple context-free word problems, and it is a long-standing open question as to where to place the word problems of hyperbolic groups in the formal language hierarchy. In this paper, we introduce a new language class called the parallel hyperedge replacement string languages, show that it contains all multiple context-free and ET0L languages, and lay down the foundations for future work that may be able to place the word problems of many hyperbolic groups in this class.

In Patrick Bahr: Proceedings 11th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2020), Online, 5th July 2020, Electronic Proceedings in Theoretical Computer Science 334, pp. 46–61.
Published: 8th February 2021.

ArXived at: https://dx.doi.org/10.4204/EPTCS.334.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org