On Some Complexity Results for Even Linear Languages
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917574597410816 |
|---|---|
| author | Cojocaru, Liliana |
| author_facet | Cojocaru, Liliana |
| contents | We deal with a normal form for context-free grammars, called Dyck normal form. This normal form is a syntactical restriction of the Chomsky normal form, in which the two nonterminals occurring on the right-hand side of a rule are paired nonterminals. This pairwise property, along with several other terminal rewriting conditions, makes it possible to define a homomorphism from Dyck words to words generated by a grammar in Dyck normal form. We prove that for each context-free language L, there exist an integer K and a homomorphism phi such that L=phi(D'_K), where D'_K is a subset of D_K and D_K is the one-sided Dyck language over K letters. As an application we give an alternative proof of the inclusion of the class of even linear languages in AC1. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_14303 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Some Complexity Results for Even Linear Languages Cojocaru, Liliana Formal Languages and Automata Theory Computational Complexity Logic in Computer Science 03D10, 03D15, F.1.1; F.4.1; F.4.3 We deal with a normal form for context-free grammars, called Dyck normal form. This normal form is a syntactical restriction of the Chomsky normal form, in which the two nonterminals occurring on the right-hand side of a rule are paired nonterminals. This pairwise property, along with several other terminal rewriting conditions, makes it possible to define a homomorphism from Dyck words to words generated by a grammar in Dyck normal form. We prove that for each context-free language L, there exist an integer K and a homomorphism phi such that L=phi(D'_K), where D'_K is a subset of D_K and D_K is the one-sided Dyck language over K letters. As an application we give an alternative proof of the inclusion of the class of even linear languages in AC1. |
| title | On Some Complexity Results for Even Linear Languages |
| topic | Formal Languages and Automata Theory Computational Complexity Logic in Computer Science 03D10, 03D15, F.1.1; F.4.1; F.4.3 |
| url | https://arxiv.org/abs/2401.14303 |