Computation on structures. Behavioural theory, logic, complexity

DOI10.1007/978-3-030-76020-5_15OpenAlexW3168087681MaRDI QIDQ2117601

Klaus-Dieter Schewe

Publication date: 22 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-76020-5_15

zbMATH Keywords

parallel algorithmslogictheory of computationabstract state machinescomplexity theorybehavioural theoryPTIMEcomputation on structuresinsignificant choice

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Concurrent abstract state machines
• A new thesis concerning synchronised parallel computing -- simplified parallel ASM thesis
• Elements of finite model theory.
• The ASM refinement method
• Choiceless polynomial time
• Datalog extensions for database queries and updates
• Computability, complexity, logic. Transl. from the German
• An extension of fixpoint logic with a symmetry-based choice construct
• A unifying logic for non-deterministic, parallel and concurrent abstract state machines
• Structure and complexity of relational queries
• A mathematical definition of full Prolog
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Fixpoint logics, relational machines, and computational complexity
• Abstract State Machines
• Fixed-point Logics with Nondeterministic Choice
• On polynomial time computation over unordered structures
• Evolving Algebras 1993: Lipari Guide
• A Behavioural Theory of Recursive Algorithms
• A Behavioural Theory for Reflective Sequential Algorithms
• A Logic for Reflective ASMs
• A complete logic for Database Abstract State Machines1
• Abstract state machines capture parallel algorithms
• Sequential abstract-state machines capture sequential algorithms