scientific article

Publication date: 1982

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

definability in classes of finite relational structures k-local formula languages for databases locally (first order) inseparable classes

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Information storage and retrieval of data (68P20) Quantifier elimination, model completeness, and related topics (03C10) Set theory (03E99)

Related Items

Towards a language theory for infinite N-free pomsets., Parametrised Complexity of Satisfiability in Temporal Logic, Shrinking games and local formulas, Describing parameterized complexity classes, Enumeration for FO Queries over Nowhere Dense Graphs, The monadic second order logic of graphs. VI: On several representations of graphs by relational structures, On the Ehrenfeucht-Fraïssé game in theoretical computer science, Modal and guarded characterisation theorems over finite transition systems, A logical approach to locality in pictures languages, An existential locality theorem, Modeling limits in hereditary classes: reduction and application to trees, Generalized quantifiers and pebble games on finite structures, Probabilities of First-Order Sentences about Unary Functions, The monadic second-order logic of graphs. I: Recognizable sets of finite graphs, Reachability and the power of local ordering, Computational complexity of logical theories of one successor and another unary function, Query languages for bags and aggregate functions, Finitely representable databases, Solutions and query rewriting in data exchange, Convergence in homogeneous random graphs, Queries with arithmetical constraints, Iterating on multiple collections in synchrony, Analysis and application of adaptive sampling, Compositional entailment checking for a fragment of separation logic, First-order Logic with Connectivity Operators, First-order limits, an analytical perspective, On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic, A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth, Efficient First-Order Model-Checking Using Short Labels, Expressive power of SQL., Model-checking hierarchical structures, Incremental recomputation in local languages., On the power of tree-walking automata., Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes, Locality and modular Ehrenfeucht-Fraïssé games, An optimal construction of Hanf sentences, Unnamed Item, Non-parametric learning of embeddings for relational data using Gaifman locality theorem, Unnamed Item, Language Games, First-order spectra with one variable, Unnamed Item, Practical algorithms for MSO model-checking on tree-decomposable graphs, First-Order Model-Checking in Random Graphs and Complex Networks, Monadic partition logics and finite automata, On the expressive power of counting, Expressive power of entity-linking frameworks, Logical limit laws for minor-closed classes of graphs, Infinitary logics and 0-1 laws, Inherent complexity of recursive queries, Logical aspects of Cayley-graphs: the group case, Expressive power of existential first-order sentences of Büchi's sequential calculus, Unnamed Item, Unnamed Item, The parameterized complexity of \(k\)-edge induced subgraphs, Infinitary logic for computer science, Modal characterisation theorems over special classes of frames, A technique for proving decidability of containment and equivalence of linear constraint queries, Computing with graph rewriting systems with priorities, Constructing decidable graphs from decidable structures, EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES, On winning strategies in Ehrenfeucht-Fraïssé games, Conversation and Games, Logic, semigroups and automata on words, Categoricity over P for first order T or categoricity for \(\phi\) \(\in {\mathcal L}_{\omega_ 1\omega}\) can stop at \(\aleph_ k\) while holding for \(\aleph_ 0,\dots ,\aleph_{k-1}\), Verifiable properties of database transactions, Local properties of query languages, On the complexity of reasoning about opinion diffusion under majority dynamics, Conjunctive-query containment and constraint satisfaction, Lower bounds for invariant queries in logics with counting., Decision problems in a logic for reasoning about reconfigurable distributed systems