arXiv Open Access 2022

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

Jürgen Dassow Bianca Truthe

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.FL

Penulis (2)

Jürgen Dassow

Bianca Truthe

Format Sitasi

APA MLA BibTeX

Dassow, J., Truthe, B. (2022). On the Generative Capacity of Contextual Grammars with Strictly Locally Testable Selection Languages. https://arxiv.org/abs/2208.14725

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2022
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓