Results 231 to 240 of about 2,112 (254)
Some of the next articles are maybe not open access.
The expressivity of XPath with transitive closure
Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2006We extend Core XPath, the navigational fragment of XPath 1.0, with transitive closure and path equalities. The resulting language, Regular XPATH≈, is expressively complete for FO* (first-order logic extended with a transitive closure operator that can be applied to formulas with exactly two free variables). As a corollary, we obtain that Regular XPATH≈
openaire +3 more sources
Complementation and Transitive Closure
1999Over infinite structures, there is a strict hierarchy of languages that is obtained by alternating uses of the least-fixed point operator and negation. For finite structures, we show that the hierarchy collapses to its first-level.
openaire +2 more sources
2005
We present Ehrenfeucht-Fraisse games for transitive closure logic (FO + TC) and for quantifier classes in (FO + TC). With this method we investigate the fine structure of positive transitive closure logic (FO + pos TC), and identify an infinite quantifier hierarchy inside (FO + pos TC), formed by interleaving universal quantifiers and TC-operators.
openaire +2 more sources
We present Ehrenfeucht-Fraisse games for transitive closure logic (FO + TC) and for quantifier classes in (FO + TC). With this method we investigate the fine structure of positive transitive closure logic (FO + pos TC), and identify an infinite quantifier hierarchy inside (FO + pos TC), formed by interleaving universal quantifiers and TC-operators.
openaire +2 more sources
Algorithms for the computation of T-transitive closures
IEEE Transactions on Fuzzy Systems, 2002We present two weight-driven algorithms for the computation of the T-transitive closure of a symmetric binary fuzzy relation on a finite universe X with cardinality n (or, equivalently, of a symmetric (n/spl times/n)-matrix with elements in [0, 1]), with T a triangular norm.
H. De Meyer, Helga Naessens, B. De Baets
openaire +1 more source
Modal Logics with Transitive Closure [PDF]
, 2014 This last chapter is about the model construction problem in classes of models having relations that are transitive closures of other relations. The main such logics are linear-time temporal logic LTL and propositional dynamic logic PDL. These logics require both blocking and model checking.
Andreas Herzig +3 more
openaire +1 more source
On the existence and construction of T-transitive closures
Information Sciences, 2003In this paper, it is shown that any fuzzy relation R on an arbitrary universe X has a T - transitive closure. The triangular norm T involved is not subject to any conditions. This existential result can be turned into an explicit expression in the case of a left-continuous triangular norm T .
H. De Meyer, B. De Baets
openaire +2 more sources
On computing the transitive closure of a state transition relation
Proceedings of the 30th international on Design automation conference - DAC '93, 1993We describe a new, recursive-descent procedure for the computation of the transitive closure of a transition relation. This procedure is the classic binary matrix procedure of [1], adapted to a BDD data structure. We demonstrate its efficacy when compared to standard iterative methods.
Robert K. Brayton +2 more
openaire +2 more sources
Polynomial Space and Transitive Closure
SIAM Journal on Computing, 1979A characterization of PSPACE in terms of the regular sets and certain algebraic closure operations is developed. It is shown that NP = PSPACE if and only if NP is closed under a form of the transitive closure operation.
openaire +1 more source
The transitive closure of a random digraph
Random Structures & Algorithms, 1990AbstractIn a random n‐vertex digraph, each arc is present with probability p, independently of the presence or absence of other arcs. We investigate the structure of the strong components of a random digraph and present an algorithm for the construction of the transitive closure of a random digraph.
openaire +2 more sources
The input/output complexity of transitive closure
Proceedings of the 1990 ACM SIGMOD international conference on Management of data, 1990Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holding s “values” is available, and that s lies between n ,
Jeffrey D. Ullman, Mihalis Yannakakis
openaire +3 more sources