On the Generative Capacity of Contextual Grammars with Strictly Locally Testable Selection Languages

Jürgen Dassow
(Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg)
Bianca Truthe
(Institut für Informatik, Universität Giessen)

We continue the research on the generative capacity of contextual grammars where contexts are adjoined around whole words (externally) or around subwords (internally) which belong to special regular selection languages. All languages generated by contextual grammars where all selection languages are elements of a certain subregular language family form again a language family. We investigate contextual grammars with strictly locally testable selection languages and compare those families to families which are based on finite, monoidal, nilpotent, combinational, definite, suffix-closed, ordered, commutative, circular, non-counting, power-separating, or union-free languages.

In Henning Bordihn, Géza Horváth and György Vaszil: Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2022), Debrecen, Hungary, August 26-27, 2022, Electronic Proceedings in Theoretical Computer Science 367, pp. 65–80.
Published: 27th August 2022.

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