scientific article; zbMATH DE number 965572

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

Publication date: 14 January 1997

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

survey computational complexity undecidability first-order logic decidability

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 (only showing first 100 items - show all)

Trees, grids, and MSO decidability: from graphs to matroids ⋮ On the data complexity of consistent query answering ⋮ Static analysis of navigational XPath over graph databases ⋮ A decidable and expressive fragment of Many-Sorted first-order linear temporal logic ⋮ A Logical Approach to Data-Aware Automated Sequence Generation ⋮ Decision procedures for flat array properties ⋮ Succinct definitions in the first order theory of graphs ⋮ On the complexity of decision using destinies in \(H\)-bounded structures ⋮ Arithmetical definability and computational complexity ⋮ Combining Theories: The Ackerman and Guarded Fragments ⋮ Symbioses between mathematical logic and computer science ⋮ Combining Model Checking and Deduction ⋮ Second-Order Quantifier Elimination on Relational Monadic Formulas – A Basic Method and Some Less Expected Applications ⋮ Complexity of finite-variable fragments of propositional temporal and modal logics of computation ⋮ Extended First-Order Logic ⋮ Controlled query evaluation with open queries for a decidable relational submodel ⋮ Undecidability of the Logic of Overlap Relation over Discrete Linear Orderings ⋮ Small model property reflects in games and automata ⋮ On Satisfiability in ATL with Strategy Contexts ⋮ The Bernays-Schönfinkel-Ramsey class for set theory: decidability ⋮ Data-complexity of the two-variable fragment with counting quantifiers ⋮ On decidability properties of local sentences ⋮ Deciding Boolean algebra with Presburger arithmetic ⋮ An automata-theoretic approach to constraint LTL ⋮ A description logic based situation calculus ⋮ FO(ID) as an extension of DL with rules ⋮ Specification and verification of data-driven Web applications ⋮ Metafinite model theory ⋮ Decidable Fragments of Many-Sorted Logic ⋮ Monadic Fragments of Gödel Logics: Decidability and Undecidability Results ⋮ How Many Legs Do I Have? Non-Simple Roles in Number Restrictions Revisited ⋮ A survey on temporal logics for specifying and verifying real-time systems ⋮ Integrity constraints for XML ⋮ Undecidability of domino games and hhp-bisimilarity. ⋮ On the almighty wand ⋮ Decidable cases of first-order temporal logic with functions ⋮ Expressive Power and Decidability for Memory Logics ⋮ Complexity of hybrid logics over transitive frames ⋮ Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions ⋮ Inseparability and Conservative Extensions of Description Logic Ontologies: A Survey ⋮ Computational complexity of theories of a binary predicate with a small number of variables ⋮ Set-syllogistics meet combinatorics ⋮ Semiring programming: a semantic framework for generalized sum product problems ⋮ Verification of multi-linked heaps ⋮ Testable and untestable classes of first-order formulae ⋮ Logical foundations of information disclosure in ontology-based data integration ⋮ On logics with two variables ⋮ Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus ⋮ Simultaneous rigid E-unification and other decision problems related to the Herbrand theorem ⋮ Modal definability of first-order formulas with free variables and query answering ⋮ Spatial reasoning with \(\mathcal{RCC} 8\) and connectedness constraints in Euclidean spaces ⋮ On the Almighty Wand ⋮ A decidable two-sorted quantified fragment of set theory with ordered pairs and some undecidable extensions ⋮ Automated reformulation of specifications by safe delay of constraints ⋮ Temporal prepositions and their logic ⋮ A SAT-based parser and completer for pictures specified by tiling ⋮ Stratified guarded first-order transition systems ⋮ Bounded Quantifier Instantiation for Checking Inductive Invariants ⋮ Topological complexity of locally finite \(\omega\)-languages ⋮ The fluted fragment with transitive relations ⋮ First-order rewritability of ontology-mediated queries in linear temporal logic ⋮ Optimal Tableau Systems for Propositional Neighborhood Logic over All, Dense, and Discrete Linear Orders ⋮ Aperiodic tilings and entropy ⋮ On the complexity of propositional and relational credal networks ⋮ The dark side of interval temporal logic: marking the undecidability border ⋮ Infinite games with finite knowledge gaps ⋮ Relational completeness of query languages for annotated databases ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ Herbrand's theorem and term induction ⋮ Definability and decidability of binary predicates for time granularity ⋮ Axiomatizing the logical core of XPath 2.0 ⋮ Local rules and global order, or aperiodic tilings ⋮ Decidability and Undecidability in Probability Logic ⋮ Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates ⋮ Inclusion dependencies and their interaction with functional dependencies in SQL ⋮ On the relationship between the complexity of decidability and decomposability of first-order theories ⋮ Infinite games on finitely coloured graphs with applications to automata on infinite trees ⋮ From Hilbert's program to a logic tool box ⋮ Exploiting functional dependencies in declarative problem specifications ⋮ Optimizing the region algebra is PSPACE-complete ⋮ On coarser interval temporal logics ⋮ Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter ⋮ Decidable fragments of many-sorted logic ⋮ The recognizability of sets of graphs is a robust property ⋮ Guarded fragments with constants ⋮ Hybrid logic meets IF modal logic ⋮ Logical separability of labeled data examples under ontologies ⋮ The undecidability of iterated modal relativization ⋮ Axiomatizing the monodic fragment of first-order temporal logic ⋮ Path constraints in semistructured databases ⋮ Relational transducers for electronic commerce ⋮ Decidable fragments of first-order temporal logics ⋮ Logic with equality: Partisan corroboration and shifted pairing ⋮ Thue trees ⋮ Rewriting queries using views over monadic database schemas ⋮ Algebraic model checking for discrete linear dynamical systems ⋮ The \(\exists\forall^2\) fragment of the first-order theory of atomic set constraints is \(\Pi_1^0\)-hard ⋮ Communities and ancestors associated with Egon Börger and ASM ⋮ Some thoughts on computational models: from massive human computing to abstract state machines, and beyond ⋮ Computation on structures. Behavioural theory, logic, complexity

This page was built for publication: