EUVIMEDOpdag EUVIMED
Open access · CC BY 4.0

Algorithmic Problems for Computation Trees

Mikhail Moshkov

Logics · 2025

DOI: 10.3390/logics3020004 ↗

At a glance

Journal article in Logics, 2025. Written by Mikhail Moshkov. Cited 2 times so far (Crossref); 11 references. The full text is freely available (open access, CC BY 4.0). Funded by: King Abdullah University of Science and Technology.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

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.

Funding

  • King Abdullah University of Science and Technology

Cite

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}
}
Start for free →