Algorithmic Problems for Computation Trees
Logics · 2025
DOI: 10.3390/logics3020004 ↗Kurz gefasst
Fachartikel in der Zeitschrift Logics, 2025. Verfasst von Mikhail Moshkov. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 11 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: King Abdullah University of Science and Technology.
Abstract (Originalsprache)
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.
Förderung
- King Abdullah University of Science and Technology
Zitieren
APA
Moshkov, M. (2025). Algorithmic Problems for Computation Trees. Logics. https://doi.org/10.3390/logics3020004
Vancouver
Moshkov M. Algorithmic Problems for Computation Trees. Logics. 2025. doi:10.3390/logics3020004
BibTeX
@article{Moshkov2025,
author = {Moshkov, Mikhail},
title = {Algorithmic Problems for Computation Trees},
journal = {Logics},
year = {2025},
doi = {10.3390/logics3020004}
}
EUVIMED