Some Remarks on First-Order Definable Tree Languages
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917709186334720 |
|---|---|
| author | Blumensath, Achim |
| author_facet | Blumensath, Achim |
| contents | We study the question of whether a given regular language of finite trees can be defined in first-order logic. We develop an algebraic approach to address this question and we use it to derive several necessary and sufficient conditions for definability (but unfortunately no condition that is both). The main difference of our results to those from the literature is that our conditions are decidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_01169 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Some Remarks on First-Order Definable Tree Languages Blumensath, Achim Formal Languages and Automata Theory We study the question of whether a given regular language of finite trees can be defined in first-order logic. We develop an algebraic approach to address this question and we use it to derive several necessary and sufficient conditions for definability (but unfortunately no condition that is both). The main difference of our results to those from the literature is that our conditions are decidable. |
| title | Some Remarks on First-Order Definable Tree Languages |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2407.01169 |