CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages

Alexander Meduna
(Department of Information Systems, Faculty of Information Technology, Brno University of Technology) 		Jakub Martiško
(Department of Information Systems, Faculty of Information Technology, Brno University of Technology)

The L(PSCG)=L(CS) problem asks whether propagating scattered context grammars and context sensitive grammars are equivalent. The presented paper reformulates and answers this problem in terms of CD grammar systems. More specifically, it characterizes the family of context sensitive languages by two-component CD grammar systems with propagating scattered context rules.

In Erzsébet Csuhaj-Varjú, Pál Dömösi and György Vaszil: Proceedings 15th International Conference on Automata and Formal Languages (AFL 2017), Debrecen, Hungary, September 4-6, 2017, Electronic Proceedings in Theoretical Computer Science 252, pp. 170–179.
Published: 21st August 2017.
ArXived at: https://dx.doi.org/10.4204/EPTCS.252.17 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org