Algorithmic Problems for Computation Trees
In this paper, we study three algorithmic problems involving computation trees: the optimization, solvability, and satisfiability problems. The solvability problem is concerned with recognizing computation trees that solve problems. The satisfiability problem is concerned with recognizing sentences...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-05-01
|
| Series: | Logics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2813-0405/3/2/4 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849431935965724672 |
|---|---|
| author | Mikhail Moshkov |
| author_facet | Mikhail Moshkov |
| author_sort | Mikhail Moshkov |
| collection | DOAJ |
| description | In this paper, we study three algorithmic problems involving computation trees: the optimization, solvability, and satisfiability problems. The solvability problem is concerned with recognizing computation trees that solve problems. The satisfiability problem is concerned with recognizing sentences that are true in at least one structure from a given set of structures. We study how the decidability of the optimization problem depends on the decidability of the solvability and satisfiability problems. We also consider various examples with both decidable and undecidable solvability and satisfiability problems. |
| format | Article |
| id | doaj-art-77069a9ec7c94a578ed47fc18fb6f856 |
| institution | Kabale University |
| issn | 2813-0405 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Logics |
| spelling | doaj-art-77069a9ec7c94a578ed47fc18fb6f8562025-08-20T03:27:29ZengMDPI AGLogics2813-04052025-05-0132410.3390/logics3020004Algorithmic Problems for Computation TreesMikhail Moshkov0Computer, Electrical and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi ArabiaIn this paper, we study three algorithmic problems involving computation trees: the optimization, solvability, and satisfiability problems. The solvability problem is concerned with recognizing computation trees that solve problems. The satisfiability problem is concerned with recognizing sentences that are true in at least one structure from a given set of structures. We study how the decidability of the optimization problem depends on the decidability of the solvability and satisfiability problems. We also consider various examples with both decidable and undecidable solvability and satisfiability problems.https://www.mdpi.com/2813-0405/3/2/4structurecomputation treeoptimization |
| spellingShingle | Mikhail Moshkov Algorithmic Problems for Computation Trees Logics structure computation tree optimization |
| title | Algorithmic Problems for Computation Trees |
| title_full | Algorithmic Problems for Computation Trees |
| title_fullStr | Algorithmic Problems for Computation Trees |
| title_full_unstemmed | Algorithmic Problems for Computation Trees |
| title_short | Algorithmic Problems for Computation Trees |
| title_sort | algorithmic problems for computation trees |
| topic | structure computation tree optimization |
| url | https://www.mdpi.com/2813-0405/3/2/4 |
| work_keys_str_mv | AT mikhailmoshkov algorithmicproblemsforcomputationtrees |