Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.01820 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915089359044608 |
|---|---|
| author | Moshkov, Mikhail |
| author_facet | Moshkov, Mikhail |
| contents | In this paper, we study classes of structures and individual structures for which programs implementing functions defined everywhere are equivalent to finite tree-programs. The programs under consideration may have cycles and at most countably many nodes. We start with programs in which arbitrary terms of a given signature may be used in function nodes and arbitrary formulas of this signature may be used in predicate nodes. We then extend our results to programs that are close in nature to computation trees: if such a program is a finite tree-program, then it is an ordinary computation tree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_01820 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Programs Versus Finite Tree-Programs Moshkov, Mikhail Logic in Computer Science In this paper, we study classes of structures and individual structures for which programs implementing functions defined everywhere are equivalent to finite tree-programs. The programs under consideration may have cycles and at most countably many nodes. We start with programs in which arbitrary terms of a given signature may be used in function nodes and arbitrary formulas of this signature may be used in predicate nodes. We then extend our results to programs that are close in nature to computation trees: if such a program is a finite tree-program, then it is an ordinary computation tree. |
| title | Programs Versus Finite Tree-Programs |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2501.01820 |