Results 21 to 30 of about 3,400 (241)
The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs [PDF]
Logical Methods in Computer Science, 2022 We study the problem of query evaluation on probabilistic graphs, namely, tuple-independent probabilistic databases over signatures of arity two. We focus on the class of queries closed under homomorphisms, or, equivalently, the infinite unions of ...
Antoine Amarilli, İsmail İlkan Ceylan
doaj +1 more source
Characteristic Sequence of Strongly Minimal Directed Single Graphs of 1-Arity
Computation, 2022 In this paper, we will classify the strongly minimal directed single graphs of 1-arity by axiomatizing the theory of characteristic sequence of such a graph. Then we will show this theory is complete by using Łos-Vaught test. Complete theory is important
Abeer M. Albalahi
doaj +1 more source
Universal Horn Sentences and the Joint Embedding Property [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 The finite models of a universal sentence $\Phi$ in a finite relational signature are the age of a structure if and only if $\Phi$ has the joint embedding property. We prove that the computational problem whether a given universal sentence $\Phi$ has the
Manuel Bodirsky +2 more
doaj +1 more source
On Safety of Unary and Non-unary IFP-operators
Моделирование и анализ информационных систем, 2018 In this paper, we investigate the safety of unary inflationary fixed point operators (IFPoperators). The safety is a computability in finitely many steps.
Sergey Dudakov
doaj +1 more source
Initial Semantics for Strengthened Signatures [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 We give a new general definition of arity, yielding the companion notions of signature and associated syntax. This setting is modular in the sense requested by Ghani and Uustalu: merging two extensions of syntax corresponds to building an amalgamated sum.
André Hirschowitz, Marco Maggesi
doaj +1 more source
, 2013 peer reviewedWe propose a parametrized version of arity gap. The parametrized arity gap gap(f,l) of a function f: Aⁿ → B measures the minimum decrease in the number of essential variables of f when l consecutive identifications of pairs of essential ...
Couceiro Miguel +5 more
core +1 more source
On the Expressiveness of Intensional Communication [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 The expressiveness of communication primitives has been explored in a common framework based on the pi-calculus by considering four features: synchronism (asynchronous vs synchronous), arity (monadic vs polyadic data), communication medium (shared ...
Thomas Given-Wilson
doaj +1 more source
Around the root of random multidimensional quadtrees [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 We analyse the distribution of the root pattern of randomly grown multidimensional point quadtrees. In particular, exact, recursive and asymptotic formulas are given for the expected arity of the root.
Gilbert Labelle +2 more
doaj +1 more source
Arity-Generic Datatype-Generic Programming [PDF]
, 2010 Some programs are doubly-generic. For example, map is datatypegeneric in that many different data structures support a mapping operation. A generic programming language like Generic Haskell can use a single definition to generate map for each type ...
Stephanie Weirich +3 more
core +1 more source
Tighter Bounds for Query Answering with Guarded TGDs [PDF]
Logical Methods in Computer ScienceWe consider the complexity of the open-world query answering problem, where we wish to determine certain answers to conjunctive queries over incomplete datasets specified by an initial set of facts and a set of guarded TGDs.
Antoine Amarilli, Michael Benedikt
doaj +1 more source