Search

Your search keyword '"Gyssens, Marc"' showing total 298 results
Start Over Author "Gyssens, Marc"

Refine your results

298 results on '"Gyssens, Marc"'

1. On matrices and $K$-relations

Author

Brijder, Robert, Gyssens, Marc, and Bussche, Jan Van den

Subjects
Computer Science - Databases, Computer Science - Logic in Computer Science
Abstract

We show that the matrix query language $\mathsf{MATLANG}$ corresponds to a natural fragment of the positive relational algebra on $K$-relations. The fragment is defined by introducing a composition operator and restricting $K$-relation arities to two. We then proceed to show that $\mathsf{MATLANG}$ can express all matrix queries expressible in the positive relational algebra on $K$-relations, when intermediate arities are restricted to three. Thus we offer an analogue, in a model with numerical data, to the situation in classical logic, where the algebra of binary relations is equivalent to first-order logic with three variables., Comment: 17 pages, 3 figures

Published
2019

3. Comparing Downward Fragments of the Relational Calculus with Transitive Closure on Trees

Author

Hellings, Jelle, Gyssens, Marc, Wu, Yuqing, Van Gucht, Dirk, Bussche, Jan Van den, Vansummeren, Stijn, and Fletcher, George H. L.

Subjects
Computer Science - Databases
Abstract

Motivated by the continuing interest in the tree data model, we study the expressive power of downward navigational query languages on trees and chains. Basic navigational queries are built from the identity relation and edge relations using composition and union. We study the effects on relative expressiveness when we add transitive closure, projections, coprojections, intersection, and difference; this for boolean queries and path queries on labeled and unlabeled structures. In all cases, we present the complete Hasse diagram. In particular, we establish, for each query language fragment that we study on trees, whether it is closed under difference and intersection.

Published
2018

6. Query Reverse Engineering in the Context of the Semantic Web: A State-of-the-Art

Author

Tabares-Martín, Leandro, Silega-Martínez, Nemury, Gyssens, Marc, Filipe, Joaquim, Editorial Board Member, Ghosh, Ashish, Editorial Board Member, Prates, Raquel Oliveira, Editorial Board Member, Zhou, Lizhu, Editorial Board Member, Singh, Pradeep Kumar, editor, Veselov, Gennady, editor, Vyatkin, Valeriy, editor, Pljonkin, Anton, editor, Dodero, Juan Manuel, editor, and Kumar, Yugal, editor

Published
2021
Full Text
View/download PDF

7. On Matrices and K-Relations

Author

Brijder, Robert, Gyssens, Marc, Van den Bussche, Jan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Herzig, Andreas, editor, and Kontinen, Juha, editor

Published
2020
Full Text
View/download PDF

8. Structural characterizations of the navigational expressiveness of relation algebras on a tree

Author

Fletcher, George H. L., Gyssens, Marc, Paredaens, Jan, Van Gucht, Dirk, and Wu, Yuqing

Subjects
Computer Science - Databases, Computer Science - Logic in Computer Science
Abstract

Given a document D in the form of an unordered node-labeled tree, we study the expressiveness on D of various basic fragments of XPath, the core navigational language on XML documents. Working from the perspective of these languages as fragments of Tarski's relation algebra, we give characterizations, in terms of the structure of D, for when a binary relation on its nodes is definable by an expression in these algebras. Since each pair of nodes in such a relation represents a unique path in D, our results therefore capture the sets of paths in D definable in each of the fragments. We refer to this perspective on language semantics as the "global view." In contrast with this global view, there is also a "local view" where one is interested in the nodes to which one can navigate starting from a particular node in the document. In this view, we characterize when a set of nodes in D can be defined as the result of applying an expression to a given node of D. All these definability results, both in the global and the local view, are obtained by using a robust two-step methodology, which consists of first characterizing when two nodes cannot be distinguished by an expression in the respective fragments of XPath, and then bootstrapping these characterizations to the desired results., Comment: 58 Pages

Published
2015

10. On the Conditional Independence Implication Problem: A Lattice-Theoretic Approach

Author

Niepert, Mathias, Van Gucht, Dirk, and Gyssens, Marc

Subjects
Computer Science - Artificial Intelligence, Computer Science - Logic in Computer Science
Abstract

A lattice-theoretic framework is introduced that permits the study of the conditional independence (CI) implication problem relative to the class of discrete probability measures. Semi-lattices are associated with CI statements and a finite, sound and complete inference system relative to semi-lattice inclusions is presented. This system is shown to be (1) sound and complete for saturated CI statements, (2) complete for general CI statements, and (3) sound and complete for stable CI statements. These results yield a criterion that can be used to falsify instances of the implication problem and several heuristics are derived that approximate this "lattice-exclusion" criterion in polynomial time. Finally, we provide experimental results that relate our work to results obtained from other existing inference algorithms., Comment: Appears in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI2008)

Published
2014

11. Relative Expressive Power of Navigational Querying on Graphs

Author

Fletcher, George H. L., Gyssens, Marc, Leinders, Dirk, Surinx, Dimitri, Bussche, Jan Van den, Van Gucht, Dirk, Vansummeren, Stijn, and Wu, Yuqing

Subjects
Computer Science - Databases, Computer Science - Logic in Computer Science
Abstract

Motivated by both established and new applications, we study navigational query languages for graphs (binary relations). The simplest language has only the two operators union and composition, together with the identity relation. We make more powerful languages by adding any of the following operators: intersection; set difference; projection; coprojection; converse; and the diversity relation. All these operators map binary relations to binary relations. We compare the expressive power of all resulting languages. We do this not only for general path queries (queries where the result may be any binary relation) but also for boolean or yes/no queries (expressed by the nonemptiness of an expression). For both cases, we present the complete Hasse diagram of relative expressiveness. In particular the Hasse diagram for boolean queries contains some nontrivial separations and a few surprising collapses., Comment: An extended abstract announcing the results of this paper was presented at the 14th International Conference on Database Theory, Uppsala, Sweden, March 2011

Published
2014
Full Text
View/download PDF

14. First-Order Definable Counting-Only Queries

Author

Hellings, Jelle, Gyssens, Marc, Van Gucht, Dirk, Wu, Yuqing, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Ferrarotti, Flavio, editor, and Woltran, Stefan, editor

Published
2018
Full Text
View/download PDF

15. The Power of Tarski’s Relation Algebra on Trees

Author

Hellings, Jelle, Wu, Yuqing, Gyssens, Marc, Van Gucht, Dirk, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Ferrarotti, Flavio, editor, and Woltran, Stefan, editor

Published
2018
Full Text
View/download PDF

16. Similarity and bisimilarity notions appropriate for characterizing indistinguishability in fragments of the calculus of relations

Author

Fletcher, George H. L., Gyssens, Marc, Leinders, Dirk, Bussche, Jan Van den, Van Gucht, Dirk, and Vansummeren, Stijn

Subjects
Computer Science - Logic in Computer Science, Computer Science - Databases
Abstract

Motivated by applications in databases, this paper considers various fragments of the calculus of binary relations. The fragments are obtained by leaving out, or keeping in, some of the standard operators, along with some derived operators such as set difference, projection, coprojection, and residuation. For each considered fragment, a characterization is obtained for when two given binary relational structures are indistinguishable by expressions in that fragment. The characterizations are based on appropriately adapted notions of simulation and bisimulation., Comment: 36 pages, Journal of Logic and Computation 2014

Published
2012
Full Text
View/download PDF

17. On the Conditional Independence Implication Problem: A Lattice-Theoretic Approach

Author

Niepert, Mathias, Van Gucht, Dirk, and Gyssens, Marc

Subjects
Computer Science - Artificial Intelligence, Computer Science - Discrete Mathematics
Abstract

A lattice-theoretic framework is introduced that permits the study of the conditional independence (CI) implication problem relative to the class of discrete probability measures. Semi-lattices are associated with CI statements and a finite, sound and complete inference system relative to semi-lattice inclusions is presented. This system is shown to be (1) sound and complete for saturated CI statements, (2) complete for general CI statements, and (3) sound and complete for stable CI statements. These results yield a criterion that can be used to falsify instances of the implication problem and several heuristics are derived that approximate this "lattice-exclusion" criterion in polynomial time. Finally, we provide experimental results that relate our work to results obtained from other existing inference algorithms.

Published
2008

18. On Typechecking Top-Down XML Tranformations: Fixed Input or Output Schemas

Author

Martens, Wim, Neven, Frank, and Gyssens, Marc

Subjects
Computer Science - Databases, Computer Science - Programming Languages
Abstract

Typechecking consists of statically verifying whether the output of an XML transformation always conforms to an output type for documents satisfying a given input type. In this general setting, both the input and output schema as well as the transformation are part of the input for the problem. However, scenarios where the input or output schema can be considered to be fixed, are quite common in practice. In the present work, we investigate the computational complexity of the typechecking problem in the latter setting.

Published
2006

21. Implication and Axiomatization of Functional Constraints on Patterns with an Application to the RDF Data Model

Author

Hellings, Jelle, Gyssens, Marc, Paredaens, Jan, Wu, Yuqing, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Beierle, Christoph, editor, and Meghini, Carlo, editor

Published
2014
Full Text
View/download PDF

23. The Impact of Transitive Closure on the Boolean Expressiveness of Navigational Query Languages on Graphs

Author

Fletcher, George H. L., Gyssens, Marc, Leinders, Dirk, Van den Bussche, Jan, Van Gucht, Dirk, Vansummeren, Stijn, Wu, Yuqing, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Lukasiewicz, Thomas, editor, and Sali, Attila, editor

Published
2012
Full Text
View/download PDF

25. Regular Expressions with Counting: Weak versus Strong Determinism

Author

Gelade, Wouter, Gyssens, Marc, Martens, Wim, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Královič, Rastislav, editor, and Niwiński, Damian, editor

Published
2009
Full Text
View/download PDF

26. A Study of a Positive Fragment of Path Queries: Expressiveness, Normal Form, and Minimization

Author

Wu, Yuqing, Van Gucht, Dirk, Gyssens, Marc, Paredaens, Jan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Sexton, Alan P., editor

Published
2009
Full Text
View/download PDF

28. The Identification of Dynamic Gene-Protein Networks

Author

Westra, Ronald L., Hollanders, Goele, Bex, Geert Jan, Gyssens, Marc, Tuyls, Karl, Istrail, Sorin, editor, Pevzner, Pavel, editor, Waterman, Michael S., editor, Tuyls, Karl, editor, Westra, Ronald, editor, Saeys, Yvan, editor, and Nowé, Ann, editor

Published
2007
Full Text
View/download PDF

29. A Methodology for Coupling Fragments of XPath with Structural Indexes for XML Documents

Author

Fletcher, George H. L., Van Gucht, Dirk, Wu, Yuqing, Gyssens, Marc, Brenes, Sofía, Paredaens, Jan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Arenas, Marcelo, editor, and Schwartzbach, Michael I., editor

Published
2007
Full Text
View/download PDF

30. On Phase Transitions in Learning Sparse Networks

Author

Hollanders, Goele, Bex, Geert Jan, Gyssens, Marc, Westra, Ronald L., Tuyls, Karl, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Kok, Joost N., editor, Koronacki, Jacek, editor, Mantaras, Raomon Lopez de, editor, Matwin, Stan, editor, Mladenič, Dunja, editor, and Skowron, Andrzej, editor

Published
2007
Full Text
View/download PDF

37. A test for tractability

Author

Jeavons, Peter, Cohen, David, Gyssens, Marc, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, and Freuder, Eugene C., editor

Published
1996
Full Text
View/download PDF

48. On the expressive power of the relational algebra on finite sets of relation pairs

Author

Fletcher, George H.L., Gyssens, Marc, Paredaens, Jan, and Van Gucht, Dirk

Subjects
Digital mapping -- Analysis, Query languages -- Analysis, Business, Computers, Electronics, Electronics and electrical industries
Abstract

We give a language-independent characterization of the expressive power of the relational algebra on finite sets of source-target relation instance pairs. The associated decision problem is shown to be cograph-isomorphism hard and in coNP. The main result is also applied in providing a new characterization of the generic relational queries. Index Terms--Query languages, relational algebra, data mapping, data integration, definability, expressibility, BP completeness, graph isomorphism, genericity, monotonicity.

Published
2009

Catalog

Books, media, physical & digital resources
See catalog results