2024/01/29 by Flavio Ferrarotti, Ferrarotti, Flavio, Klaus‐Dieter Schewe +1
Engineering · Computer Science · Decision Sciences · #Advanced Numerical Analysis Techniques #Digital Image Processing Techniques #Fuzzy and Soft Set Theory
paper · pdf · doi:10.48550/arxiv.2401.16366
Abstract State Machines (ASMs) provide a model of computations on structures rather than strings. Blass, Gurevich and Shelah showed that deterministic PTIME-bounded ASMs define the choiceless fragment of PTIME, but cannot capture PTIME. In this article deterministic PSPACE-bounded ASMs are introduced, and it is proven that they cannot capture PSPACE. The key for the proof is a characterisation by partial fixed-point formulae over the Stärk/Nanchen logic for deterministic ASMs and a construction of transitive structures, in which such formulae must hold. This construction exploits that the decisive support theorem for choiceless polynomial time holds under slightly weaker assumptions.