Search results for "relation"
showing 10 items of 10542 documents
Degree of monotonicity in aggregation process
2010
In this paper we introduce a fuzzy order relation notion in the description of aggregation process. Namely, we use the fuzzy order relation to define the degree of monotonicity, which is equal to 1 for a monotone function with respect to a crisp order relation. In that case, integration of fuzzy order relation allows us to generalize the notion of monotonicity and we try to investigate the benefits of using fuzzy relations instead of a crisp relation. Further we illustrate this definition by examples and study the properties of aggregation functions which have a certain degree of monotonicity.
Termination of a set of rules modulo a set of equations
2006
The problem of termination of a set R of rules modulo a set E of equations, called E-termination problem, arises when trying to complete the set of rules in order to get a Church-Rosser property for the rules modulo the equations. We first show here that termination of the rewriting relation and E-termination are the same whenever the used rewriting relation is E-commuting, a property inspired from Peterson and Stickel’s E-compatibility property. More precisely, their results can be obtained by requiring termination of the rewriting relation instead of E-termination if E-commutation is used instead of E-compatibility. When the rewriting relation is not E-commuting, we show how to reduce E-t…
Toward computability of trace distance discord
2014
It is known that a reliable geometric quantifier of discord-like correlations can be built by employing the so-called trace distance. This is used to measure how far the state under investigation is from the closest "classical-quantum" one. To date, the explicit calculation of this indicator for two qubits was accomplished only for states such that the reduced density matrix of the measured party is maximally mixed, a class that includes Bell-diagonal states. Here, we first reduce the required optimization for a general two-qubit state to the minimization of an explicit two-variable function. Using this framework, we show next that the minimum can be analytically worked out in a number of r…
Defining relations of minimal degree of the trace algebra of 3×3 matrices
2008
Abstract The trace algebra C n d over a field of characteristic 0 is generated by all traces of products of d generic n × n matrices, n , d ⩾ 2 . Minimal sets of generators of C n d are known for n = 2 and n = 3 for any d as well as for n = 4 and n = 5 and d = 2 . The defining relations between the generators are found for n = 2 and any d and for n = 3 , d = 2 only. Starting with the generating set of C 3 d given by Abeasis and Pittaluga in 1989, we have shown that the minimal degree of the set of defining relations of C 3 d is equal to 7 for any d ⩾ 3 . We have determined all relations of minimal degree. For d = 3 we have also found the defining relations of degree 8. The proofs are based …
On the use of relational expressions in the design of efficient algorithms
2005
Relational expressions have finite binary relations as arguments and the operations are composition (·), closure (*), inverse (−1), and union (U). The efficient computation of the relation denoted by a relational expression is considered, and a tight bound is established on the complexity of the algorithm suggested by Hunt, Szymanski and Ullman. The result implies a unified method for deriving efficient algorithms for many problems in parsing. For example, optimal algorithms are derived for strong LL(1) and strong LL(2) parser construction and an efficient polynomialtime algorithm is derived for determining the inessential error entries in an LR(1) parsing table.
ON THE STAR HEIGHT OF RATIONAL LANGUAGES
1994
Two problems concerning the star height of a rational language are investigated: the star height one problem and the relationships between the unambiguity of an expression and its star height. For this purpose we consider the class of factorial, transitive and rational (FTR) languages. From the algebraic point of view a FTR language is the set of factors of a rational submonoid M. Two subclasses of FTR languages are introduced: renewal languages, corresponding to the case of M finitely generated, and unambiguous renewal languages, corresponding to the case of M finitely generated and free. We prove that a FTR language has star height one if and only if it is renewal. This gives a simple de…
Nondeterministic operations on finite relational structures
1998
Abstract This article builds on a tutorial introduction to universal algebra for language theory (Courcelle, Theoret. Comput. Sci. 163 (1996) 1–54) and extends it in two directions. First, nondeterministic operations are considered, i.e., operations which give a set of results instead of a single one. Most of their properties concerning recognizability and equational definability carry over from the ordinary case with minor modifications. Second, inductive sets of evaluations are studied in greater detail. It seems that they are handled most naturally in the framework presented here. We consider the analogues of top-down and bottom-up tree transducers. Again, most of their closure propertie…
Fuzzy functions: a fuzzy extension of the category SET and some related categories
2000
<p>In research Works where fuzzy sets are used, mostly certain usual functions are taken as morphisms. On the other hand, the aim of this paper is to fuzzify the concept of a function itself. Namely, a certain class of L-relations F : X x Y -&gt; L is distinguished which could be considered as fuzzy functions from an L-valued set (X,Ex) to an L-valued set (Y,Ey). We study basic properties of these functions, consider some properties of the corresponding category of L-valued sets and fuzzy functions as well as briefly describe some categories related to algebra and topology with fuzzy functions in the role of morphisms.</p>
Two-Variable First-Order Logic with Equivalence Closure
2012
We consider the satisfiability and finite satisfiability problems for extensions of the two-variable fragment of first-order logic in which an equivalence closure operator can be applied to a fixed number of binary predicates. We show that the satisfiability problem for two-variable, first-order logic with equivalence closure applied to two binary predicates is in 2-NExpTime, and we obtain a matching lower bound by showing that the satisfiability problem for two-variable first-order logic in the presence of two equivalence relations is 2-NExpTime-hard. The logics in question lack the finite model property; however, we show that the same complexity bounds hold for the corresponding finite sa…
A new formulation of the loop-tree duality at higher loops
2019
We present a new formulation of the loop-tree duality theorem for higher loop diagrams valid both for massless and massive cases. $l$-loop integrals are expressed as weighted sum of trees obtained from cutting $l$ internal propagators of the loop graph. In addition, the uncut propagators gain a modified $i \delta$-prescription, named dual-propagators. In this new framework one can go beyond graphs and calculate the integrand of loop amplitudes as a weighted sum of tree graphs, which form a tree-like object. These objects can be computed efficiently via recurrence relations.