On Decidability and Expressive Power of Fusion Grammars
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915209787998208 |
|---|---|
| author | Pshenitsyn, Tikhon |
| author_facet | Pshenitsyn, Tikhon |
| contents | We study algorithmic complexity and expressive power of fusion grammars, a novel formalism introduced in [Kreowski, Kuske, and Lye 2017], which extends hyperedge replacement grammars. In the first part of the work, we prove that the non-emptiness problem for fusion grammars and the membership problem for fusion grammars without markers and connectors are decidable and are in NEXPTIME. We introduce fusion grammars with bounded usage of markers and connectors and prove decidability of the membership problem for them as well. In the proofs, we develop the technique of hypergraph vertex colourings encoded in hyperedge labels and also the technique of evidence paths and their encodings.
In the second part of the work, we study the class of languages generated by connection-preserving fusion grammars. Namely, we prove Parikh's theorem for them, i.e. we show that these languages are semilinear. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_00954 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On Decidability and Expressive Power of Fusion Grammars Pshenitsyn, Tikhon Formal Languages and Automata Theory We study algorithmic complexity and expressive power of fusion grammars, a novel formalism introduced in [Kreowski, Kuske, and Lye 2017], which extends hyperedge replacement grammars. In the first part of the work, we prove that the non-emptiness problem for fusion grammars and the membership problem for fusion grammars without markers and connectors are decidable and are in NEXPTIME. We introduce fusion grammars with bounded usage of markers and connectors and prove decidability of the membership problem for them as well. In the proofs, we develop the technique of hypergraph vertex colourings encoded in hyperedge labels and also the technique of evidence paths and their encodings. In the second part of the work, we study the class of languages generated by connection-preserving fusion grammars. Namely, we prove Parikh's theorem for them, i.e. we show that these languages are semilinear. |
| title | On Decidability and Expressive Power of Fusion Grammars |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2309.00954 |