Forbidden-Context & Ordered Grammar Systems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910156779945984 |
|---|---|
| author | Fernau, Henning Kuppusamy, Lakshmanan Schulz, Jana |
| author_facet | Fernau, Henning Kuppusamy, Lakshmanan Schulz, Jana |
| contents | In this paper, we consider combining the ideas of forbidden random context grammars as well as of ordered grammars with cooperating distributed grammar systems (CDGS). We focus on investigating their generative capacities. Both ideas can be added to CDGS in two ways: either having (e.g.) a strict order of the rules in each component, or having a strict order on the components. This leads to four different scenarios, only some of them have been addressed in the literature before. While in the area of CDGS, many inclusions among language classes have been %are still open questions for decades, the proposed addition of forbidden random context and ordered regulation variants leads to a clear picture which allows us to get down to only five different classes of languages well known from classical regulated rewriting. This way, we also solve some open problems from the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_19963 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Forbidden-Context & Ordered Grammar Systems Fernau, Henning Kuppusamy, Lakshmanan Schulz, Jana Formal Languages and Automata Theory In this paper, we consider combining the ideas of forbidden random context grammars as well as of ordered grammars with cooperating distributed grammar systems (CDGS). We focus on investigating their generative capacities. Both ideas can be added to CDGS in two ways: either having (e.g.) a strict order of the rules in each component, or having a strict order on the components. This leads to four different scenarios, only some of them have been addressed in the literature before. While in the area of CDGS, many inclusions among language classes have been %are still open questions for decades, the proposed addition of forbidden random context and ordered regulation variants leads to a clear picture which allows us to get down to only five different classes of languages well known from classical regulated rewriting. This way, we also solve some open problems from the literature. |
| title | Forbidden-Context & Ordered Grammar Systems |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2604.19963 |