The classical decision problem.

zbMath0970.03001MaRDI QIDQ5944231

Erich Grädel, Yuri Gurevich, Egon Börger

Publication date: 30 September 2001

Published in: Universitext (Search for Journal in Brave)

zbMATH Keywords

surveyundecidabilityfirst-order logicdecidabilitycomputational complexity of decidable problemsdecidable classestiling problemsundecidable classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Undecidability and degrees of sets of sentences (03D35) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (32)

A logical approach to locality in pictures languages ⋮ Ensuring Correctness of Model Transformations While Remaining Decidable ⋮ Canonization for two variables and puzzles on the square ⋮ Combining answer set programming with description logics for the semantic web ⋮ Embedding causal team languages into predicate logic ⋮ A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module ⋮ Quasiperiodicity and Non-computability in Tilings ⋮ The periodic domino problem revisited ⋮ Are bundles good deals for first-order modal logic? ⋮ Trakhtenbrot theorem and first-order axiomatic extensions of MTL ⋮ Tilings and submonoids of metabelian groups. ⋮ Query languages for data exchange: beyond unions of conjunctive queries ⋮ FLP answer set semantics without circular justifications for general logic programs ⋮ Approximations of Mappings ⋮ The light side of interval temporal logic: the Bernays-Schönfinkel fragment of CDT ⋮ VON NEUMANN’S CONSISTENCY PROOF ⋮ Effective Closed Subshifts in 1D Can Be Implemented in 2D ⋮ A sound and complete model-generation procedure for consistent and confidentiality-preserving databases ⋮ On reasoning about structural equality in XML: a description logic approach ⋮ IPL: an integration property language for multi-model cyber-physical systems ⋮ From Philosophical to Industrial Logics ⋮ Unnamed Item ⋮ \(Log_A\mathbf{G}\): an algebraic non-monotonic logic for reasoning with graded propositions ⋮ Decidable subsets of open logic and an algorithm for R-calculus ⋮ On the parameterized complexity of graph modification to first-order logic properties ⋮ Combining Consistency and Confidentiality Requirements in First-Order Databases ⋮ Combining Description Logics, Description Graphs, and Rules ⋮ Languages, Decidability, and Complexity ⋮ Weak essentially undecidable theories of concatenation ⋮ REDUCTION TECHNIQUES FOR PROVING DECIDABILITY IN LOGICS AND THEIR MEET–COMBINATION ⋮ Deciding simple infinity axiom sets with one binary relation by means of superpostulates ⋮ Some thoughts on computational models: from massive human computing to abstract state machines, and beyond

This page was built for publication: The classical decision problem.