Journalartikel

Jahr der Veröffentlichung: 2023

Zeitschrift: RAIRO: Theoretical Informatics and Applications

Bandnummer: 57

ISSN: 0988-3754

eISSN: 2804-7346

Open Access Status: Hybrid

DOI Link: https://doi.org/10.1051/ita/2023012

Verlag: EDP Sciences

Abstract: 
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 the computational capacity of 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. With these results, also an open problem regarding ordered and non-counting selection languages is solved.

Harvard-Zitierstil: Dassow, J. and Truthe, B. (2023) Relations of contextual grammars with strictly locally testable selection languages, RAIRO: Theoretical Informatics and Applications, 57, Article 10. https://doi.org/10.1051/ita/2023012

APA-Zitierstil: Dassow, J., & Truthe, B. (2023). Relations of contextual grammars with strictly locally testable selection languages. RAIRO: Theoretical Informatics and Applications. 57, Article 10. https://doi.org/10.1051/ita/2023012