Results 21 to 30 of about 2,753 (280)
Arity hierarchy for temporal logics
Theoretical Computer Science, 2008 The paper studies the expressive power of temporal logics over trees. The main result states that in contrast to Kamp's theorem (stating, inter alia, that the temporal logic with ``Until'' and ``Since'' is expressively complete for the monadic first-order logic over the linear order of natural numbers), for every \(n\) there is a modality of arity \(n\)
Alexander Rabinovich +1 more
openaire +3 more sources
Essential Arity Gap of Boolean Functions [PDF]
Serdica Journal of Computing, 2008 In this paper we investigate the Boolean functions with maximum essential arity gap. Additionally we propose a simpler proof of an important theorem proved by M. Couceiro and E. Lehtonen in [3]. They use Zhegalkin’s polynomials as normal forms for Boolean functions and describe the functions with essential arity gap equals 2.
Shtrakov, Slavcho
openaire +4 more sources
Ellipses and Lambda Definability [PDF]
Logical Methods in Computer Science, 2015 Ellipses are a meta-linguistic notation for denoting terms the size of which are specified by a meta-variable that ranges over the natural numbers. In this work, we present a systematic approach for encoding such meta-expressions in the \^I-calculus ...
Mayer Goldberg
doaj +1 more source
Minor complexity of discrete functions [PDF]
Applied Computing and Informatics, 2021 In this paper we study a class of complexity measures, induced by a new data structure for representing k-valued functions (operations), called minor decision diagram.
Slavcho Shtrakov
doaj +1 more source
The Family of Multiparameter Quaternary Subdivision Schemes
Journal of Mathematics, 2021 In the field of subdivision, the smoothness increases as the arity of schemes increases. The family of high arity schemes gives high smoothness comparative to low arity schemes.
Ghulam Mustafa +4 more
doaj +1 more source
Polyadic Analogs of Direct Product
Universe, 2022 We propose a generalization of the external direct product concept to polyadic algebraic structures which introduces novel properties in two ways: the arity of the product can differ from that of the constituents, and the elements from different ...
Steven Duplij
doaj +1 more source
Higher Regularity, Inverse and Polyadic Semigroups
Universe, 2021 We generalize the regularity concept for semigroups in two ways simultaneously: to higher regularity and to higher arity. We show that the one-relational and multi-relational formulations of higher regularity do not coincide, and each element has several
Steven Duplij
doaj +1 more source
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
A survey on the arity gap [PDF]
, 2015 International audienceThe arity gap of a function of several variables is defined as the minimum decrease in the number of essential variables when essential variables of the function are identified.
Lehtonen, Erkko +2 more
core +3 more sources
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