Context-Free Trees
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910046560976896 |
|---|---|
| author | Wächter, Jan Philipp |
| author_facet | Wächter, Jan Philipp |
| contents | Muller and Schupp introduced the concept of context-free graphs (originating from Cayley graphs of context-free groups). These graphs are always tree-like (i.e. quasi-isometric to a tree) and in this paper we investigate the subclass of bona fide context-free trees. We show that they have a finite-state description using multi-edge NFAs and that this specializes to certain partial DFAs in the case of deterministic graphs. We investigate this form of encoding algorithmically and show that the isomorphism problem for deterministic context-free trees is NL-complete in the rooted and the non-rooted case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_08624 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Context-Free Trees Wächter, Jan Philipp Formal Languages and Automata Theory Group Theory 68Q17, 68R10, 05C62, 68Q45 F.4.m Muller and Schupp introduced the concept of context-free graphs (originating from Cayley graphs of context-free groups). These graphs are always tree-like (i.e. quasi-isometric to a tree) and in this paper we investigate the subclass of bona fide context-free trees. We show that they have a finite-state description using multi-edge NFAs and that this specializes to certain partial DFAs in the case of deterministic graphs. We investigate this form of encoding algorithmically and show that the isomorphism problem for deterministic context-free trees is NL-complete in the rooted and the non-rooted case. |
| title | Context-Free Trees |
| topic | Formal Languages and Automata Theory Group Theory 68Q17, 68R10, 05C62, 68Q45 F.4.m |
| url | https://arxiv.org/abs/2603.08624 |