scientific article; zbMATH DE number 3819693
From MaRDI portal
Publication:3666827
zbMATH Open0518.03008MaRDI QIDQ3666827FDOQ3666827
Publication date: 1982
Title of this publication is not available (Why is that?)
definability in classes of finite relational structuresk-local formulalanguages for databaseslocally (first order) inseparable classes
Information storage and retrieval of data (68P20) Logic with extra quantifiers and operators (03C80) Quantifier elimination, model completeness, and related topics (03C10) Set theory (03E99)
Cited In (74)
- Lower bounds for invariant queries in logics with counting.
- An existential locality theorem
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Logical aspects of Cayley-graphs: the group case
- On the Ehrenfeucht-Fraïssé game in theoretical computer science
- Analysis and application of adaptive sampling
- Infinitary logics and 0-1 laws
- Expressive power of SQL.
- Inherent complexity of recursive queries
- Local properties of query languages
- Computing with graph rewriting systems with priorities
- Expressive power of entity-linking frameworks
- Model-checking hierarchical structures
- An optimal construction of Hanf sentences
- A technique for proving decidability of containment and equivalence of linear constraint queries
- Logical limit laws for minor-closed classes of graphs
- Verifiable properties of database transactions
- Query languages for bags and aggregate functions
- Infinitary logic for computer science
- Finitely representable databases
- Queries with arithmetical constraints
- A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth
- On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic
- 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}\)
- A logical approach to locality in pictures languages
- Towards a language theory for infinite N-free pomsets.
- Constructing decidable graphs from decidable structures
- Computational complexity of logical theories of one successor and another unary function
- The parameterized complexity of \(k\)-edge induced subgraphs
- Expressive power of existential first-order sentences of Büchi's sequential calculus
- On winning strategies in Ehrenfeucht-Fraïssé games
- On the power of tree-walking automata.
- Locality and modular Ehrenfeucht-Fraïssé games
- Decision problems in a logic for reasoning about reconfigurable distributed systems
- Conjunctive-query containment and constraint satisfaction
- First-order spectra with one variable
- Shrinking games and local formulas
- Generalized quantifiers and pebble games on finite structures
- Title not available (Why is that?)
- First-order limits, an analytical perspective
- Language Games
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Modal and guarded characterisation theorems over finite transition systems
- Parametrised Complexity of Satisfiability in Temporal Logic
- Modal characterisation theorems over special classes of frames
- Describing parameterized complexity classes
- Logic, semigroups and automata on words
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- Compositional entailment checking for a fragment of separation logic
- On the complexity of reasoning about opinion diffusion under majority dynamics
- Incremental recomputation in local languages.
- Probabilities of First-Order Sentences about Unary Functions
- Reachability and the power of local ordering
- Monadic partition logics and finite automata
- Solutions and query rewriting in data exchange
- On the expressive power of counting
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- Iterating on multiple collections in synchrony
- First-Order Model-Checking in Random Graphs and Complex Networks
- On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Non-parametric learning of embeddings for relational data using Gaifman locality theorem
- Enumeration for FO Queries over Nowhere Dense Graphs
- Title not available (Why is that?)
- Efficient First-Order Model-Checking Using Short Labels
- First-order Logic with Connectivity Operators
- EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES
- Model checking on interpretations of classes of bounded local cliquewidth
- When locality meets preservation
- Modeling limits in hereditary classes: reduction and application to trees
- Convergence in homogeneous random graphs
- Conversation and Games
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3666827)
