Decidable problems for powerful programs

DOI10.1145/3149.3157zbMath0629.68010OpenAlexW2056964218MaRDI QIDQ3766814

Eitan M. Gurari

Publication date: 1985

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3149.3157

zbMATH Keywords

computational complexityPSPACE-completecounter machinesequivalence problemfinite-memory programsPresburger setssolvable decision problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (3)

Temporal Specifications with Accumulative Values ⋮ ON THE EDGE OF DECIDABILITY IN COMPLEXITY ANALYSIS OF LOOP PROGRAMS ⋮ On the Decidability of the Equivalence Problem for Monadic Recursive Programs

This page was built for publication: Decidable problems for powerful programs