Sequential abstract-state machines capture sequential algorithms

DOI10.1145/343369.343384zbMath1365.68258OpenAlexW1998333922WikidataQ55890020 ScholiaQ55890020MaRDI QIDQ5738899

Yuri Gurevich

Publication date: 13 June 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

sequential algorithmspecificationexecutable specificationTuring's thesisabstract-state machinesequential ASM thesis

Mathematics Subject Classification ID

Related Items (56)

Distributed Adaptive Systems ⋮ A Characterization of Distributed ASMs with Partial-Order Runs ⋮ What Is an Algorithm? ⋮ Periodicity based decidable classes in a first order timed logic ⋮ Concurrent abstract state machines ⋮ Symbioses between mathematical logic and computer science ⋮ What is the Church-Turing Thesis? ⋮ In some curved spaces, one can solve NP-hard problems in polynomial time ⋮ A new thesis concerning synchronised parallel computing -- simplified parallel ASM thesis ⋮ ASM-based formal design of an adaptivity component for a cloud system ⋮ Computable execution traces ⋮ Rete Network Slicing for Model Queries ⋮ Axiomatizing Analog Algorithms ⋮ Can abstract state machines be useful in language theory? ⋮ Honest universality ⋮ Abstract State Machines for Data-Parallel Computing ⋮ Software science view on quantum circuit algorithms ⋮ The never-ending recursion ⋮ Programming in logic without logic programming ⋮ Unnamed Item ⋮ Execution trace sets for real computation ⋮ Information systems in modeling interactive computations on granules ⋮ Test generation from event system abstractions to cover their states and transitions ⋮ Operational semantics for declarative multi-paradigm languages ⋮ Algorithms: From Al-Khwarizmi to Turing and Beyond ⋮ Theses for Computation and Recursion on Concrete and Abstract Structures ⋮ Semantics-to-Syntax Analyses of Algorithms ⋮ Honest Computability and Complexity ⋮ Physical Computational Complexity and First-order Logic ⋮ The computable kernel of abstract state machines ⋮ Proving properties of the Chord protocol using the ASM formalism ⋮ Three Paths to Effectiveness ⋮ ASMs and Operational Algorithmic Completeness of Lambda Calculus ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Abstract State Machines and the Inquiry Process ⋮ Axiomatization and characterization of BSP algorithms ⋮ Is there any real substance to the claims for a ``new computationalism? ⋮ A logic for secure memory access of abstract state machines ⋮ Abstract state machines: a unifying view of models of computation and of system design frameworks ⋮ Database query processing using finite cursor machines ⋮ A unifying logic for non-deterministic, parallel and concurrent abstract state machines ⋮ Towards a Logic for Abstract MetaFinite State Machines ⋮ The Church-Turing Thesis over Arbitrary Domains ⋮ A Natural Axiomatization of Computability and Proof of Church's Thesis ⋮ Reactive Answer Set Programming ⋮ When are Two Algorithms the Same? ⋮ A Proof System with Bounded Non-determinism in Database Transformations ⋮ Formalizing Operational Semantic Specifications in Logic ⋮ A Behavioural Theory of Recursive Algorithms ⋮ A guarded fragment for abstract state machines ⋮ Semantic essence of AsmL ⋮ A Survey on Analog Models of Computation ⋮ Communities and ancestors associated with Egon Börger and ASM ⋮ ASM specification and refinement of a quantum algorithm ⋮ What is the natural abstraction level of an algorithm? ⋮ Computation on structures. Behavioural theory, logic, complexity

This page was built for publication: Sequential abstract-state machines capture sequential algorithms