Repository of the University of Hasselt containing publications in the fields of statistics, computer science, information strategies and material from the Institute for behavioural sciences.
Mostrando recursos 1 - 20 de 677
Quantifier elimination for elementary geometry and elementary affine geometry - Grimson, Rafael; Kuijpers, Bart; Othman, Walied
We introduce new first-order languages for the elementary n-dimensional geometry and elementary n-dimensional affine geometry (n >= 2), based on extending FO(beta, equivalent to) and FO(beta), respectively, with new function symbols. Here, beta stands for the betweenness relation and equivalent to for the congruence relation. We show that the associated theories admit effective quantifier elimination. (C) 2012 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
Metadata quality evaluation of a repository based on a sample technique - Goovaerts, Marc; Leinders, Dirk
In this paper, we evaluate the quality of the metadata of an OAI-compliant repository based on the completeness metric proposed by X. Ochoa and E. Duval. This study focuses on the completeness of the metadata records as defined by M.A. Sicilia et al, where machine-understandability is a mandatory requirement for completeness. The goal is to use the completeness metric as a tool for harvesters and repository managers to evaluate easily the quality of the metadata of a repository. We focus on the metadata used by the communities of agriculture, aquaculture and environment from the VOA3R project. The OceanDocs repository serves...
An argumentation framework for description logic ontology reasoning and management - Zhang, Xiaowang; Lin, Zuoquan
This paper presents an argumentation framework for reasoning and management in (inconsistent or incoherent) description logic ontologies which contain conflicts. First, a new argumentation framework obtained by combining Besnard and Hunter???s framework with binary argumentation is introduced to frame the inner relation over axioms in an ontology. A dialogue mechanism, based on this framework, is then presented to derive meaningful consequences from inconsistent ontologies. Three novel operators are developed to repair those axioms or assertions which cause inconsistency or incoherency of ontologies by using this framework. Within this framework, an inconsistency is neither directly assigned a contradictory value nor roughly...
The Relation between Order of Acquisition, Segmental Frequency and Function: The Case of Word-Initial Consonants in Dutch - Van Severen, Lieve; Gillis, Joris J.M.; Molemans, Inge; van den Berg, Renate; De Maeyer, Sven; Gillis, Steven
The impact of input frequency (IF) and functional load (FL) of segments in the ambient language on the acquisition order of word-initial consonants is investigated. Several definitions of IF/FL and their components are computed using a longitudinal corpus of interactions between 30 Dutch-speaking children (age range: 0;6???2;0) and their primary caretaker(s). The corpus study reveals significant correlations between IF/FL and acquisition order. The highest predictive values are found for the token frequency of segments, and for FL computed on minimally different word types in child-directed speech. Although IF and FL significantly correlate, they do have a different impact on the...
Expressive Power of Safe First-Order Logical Decision Trees - Gillis, Joris J.M.; Van den Bussche, Jan
This paper characterizes the expressive power of a subclass of first-order logical decision trees (FOLDTs) as a fragment of first-order logic. Specifically, using safe FOLDTs one can express precisely the boolean combinations of safe existential sentences.
Succinctness of pattern-based schema languages for XML - Gelade, Wouter; Neven, Frank
Martens et al. defined a pattern-based specification language equivalent in expressive power to the widely adopted XML Schema definitions (XSDs). This language consists of rules of the form (r, s) where r and s are regular expressions and can be seen as a type-free extension of DTDs with vertical regular expressions. Sets of such rules can be interpreted both in an existential or universal way. In the present paper, we study the succinctness of both semantics w.r.t. each other and w.r.t. the common abstraction of XSDs in terms of single-type extended DTDs. The investigation is carried out relative to three...
All normalized anti-monotonic overlap graph measures are bounded - Calders, Toon; Ramon, Jan; Van Dyck, Dries
In graph mining, a frequency measure for graphs is anti-monotonic if the frequency of a pattern never exceeds the frequency of a subpattern. The efficiency and correctness of most graph pattern miners relies critically on this property. We study the case where frequent subgraphs have to be found in one graph. Vanetik et al. (Data Min Knowl Disc 13(2):243-260, 2006) already gave sufficient and necessary conditions for anti-monotonicity of graph measures depending only on the edge-overlaps between the instances of the pattern in a labeled graph. We extend these results to homomorphisms, isomorphisms and homeomorphisms on both labeled and unlabeled,...
The Dynamic Complexity of Formal Languages - GELADE, Wouter; Marquardt, Marcel; Schwentick, Thomas
The article investigates the power of the dynamic complexity classes DYNFO, DYNQF, and DYNPROP over string languages. The latter two classes contain problems that can be maintained using quantifier-free first-order updates, with and without auxiliary functions, respectively. It is shown that the languages maintainable in DYNPROP are exactly the regular languages, even when allowing arbitrary precomputation. This enables lower bounds for DYNPROP and separates DYNPROP from DYNQF and DYNFO. Further, it is shown that any context-free language can be maintained in DYNFO and a number of specific context-free languages, for example all Dyck-languages, are maintainable in DYNQF. Furthermore, the dynamic...
Pivots, determinants, and perfect matchings of graphs - BRIJDER, Robert; Harju, Tero; Hoogeboom, Hendrik Jan
We consider sequences of local and edge complementations on graphs with loops (we allow local complementation only on looped vertices). We recall that these operations together form the matrix operation of principal pivot transform (or pivot) restricted to graphs. This fact is not well known, and as a consequence various special cases of the properties of pivot have been rediscovered multiple times. In this paper we give a gentle overview of various properties of pivot for local and edge complementations on graphs. Moreover, we relate the pivot operation to perfect matchings to obtain a purely graph-theoretical characterization of the effect...
Interactome-Wide Prediction of Protein-Protein Binding Sites Reveals Effects of Protein Sequence Variation in Arabidopsis thaliana - Leal Valentim, Felipe; Neven, Frank; Boyen, Peter; van Dijk, Aalt D. J.
The specificity of protein-protein interactions is encoded in those parts of the sequence that compose the binding interface. Therefore, understanding how changes in protein sequence influence interaction specificity, and possibly the phenotype requires knowing the location of binding sites in those sequences. However, large-scale detection of protein interfaces remains a challenge. Here, we present a sequence- and interactome-based approach to mine interaction motifs from the recently published Arabidopsis thaliana interactome. The resultant proteome-wide predictions are available via www.ab.wur.nl/sliderbio and set the stage for further investigations of protein-protein binding sites. To assess our method, we first show that, by using a...
Efficient External-Memory Bisimulation on DAGs - Hellings, Jelle; Fletcher, George H. L.; Haverkort, Herman
In this paper we introduce the first efficient external-memory algorithm to compute the bisimilarity equivalence classes of a directed acyclic graph (DAG). DAGs are commonly used to model data in a wide variety of practical applications, ranging from XML documents and data provenance models, to web taxonomies and scientific workflows. In the study of efficient reasoning over massive graphs, the notion of node bisimilarity plays a central role. For example, grouping together bisimilar nodes in an XML data set is the first step in many sophisticated approaches to building indexing data structures for efficient XPath query evaluation. To date, however,...
A Type System for DNAQL - Brijder, Robert; Gillis, Joris J.M.; Van den Bussche, Jan
Recently we have introduced a formal graph-based data model for DNA complexes geared towards database applications. The model is accompanied by the programming language DNAQL for querying databases in DNA. Due to natural restrictions on the implementability and termination of operations on DNA, programs in DNAQL are not always well defi ned on all possible inputs. Indeed, a problem left open by our previous work has been to devise a type system for DNAQL, with a soundness property to the e ect that well-typed programs are well defi ned on all inputs adhering to given input types. The contribution of...
Deciding twig-definability of node selecting tree automata - Antonopoulos, Timos; Hovland, Dag; Martens, Wim; Neven, Frank
Node selecting tree automata (NSTAs) constitute a general formalism defining unary queries over trees. Basically, a node is selected by an NSTA when it is visited in a selecting state during an accepting run. We consider twig patterns as an abstraction of XPath. Since the queries definable by NSTAs form a strict superset of twig-definable queries, we study the complexity of the problem to decide whether the query by a given NSTA is twig-definable. In particular, we obtain that the latter problem is EXPTIME-complete. In addition, we show that it is also EXPTIME-complete to de- cide whether the query by...
Developing and Analyzing XSDs through BonXai - Martens, Wim; Neven, Frank; Niewerth, Matthias; Schwentick, Thomas
BonXai is a versatile schema specification language expres- sively equivalent to XML Schema. It is not intended as a replacement for XML Schema but it can serve as an addi- tional, user-friendly front-end. It offers a simple way and a lightweight syntax to specify the context of elements based on regular expressions rather than on types. In this demo we show the front-end capabilities of BonXai and exemplify its potential to offer a novel way to view existing XML Schema Definitions. In particular, we present several usage scenarios specifically targeted to showcase the ease of specifying, mod- ifying, and understanding...
Binary Symmetric Matrix Inversion Through Local Complementation - Brijder, Robert; Hoogeboom, Hendrik Jan
We consider the Schur complement operation for symmetric matrices over GF(2), which we identify with graphs through the adjacency matrix representation. It is known that Schur complementation for such a matrix (i.e., for a graph) can be decomposed into a sequence of two types of elementary Schur complement operations: (1) local complementation on a looped vertex followed by deletion of that vertex and (2) edge complementation on an edge without looped vertices followed by deletion of that edge. We characterize the symmetric matrices over GF(2) that can be transformed into the empty matrix using only operations of (1). As a...
Mining frequent itemsets in a stream - Calders, Toon; Dexters, Nele; Gillis, Joris J.M.; Goethals, Bart
Mining frequent itemsets in a datastream proves to be a difficult problem, as itemsets arrive in rapid succession and storing parts of the stream is typically impossible. Nonetheless, it has many useful applications; e.g., opinion and sentiment analysis from social networks. Current stream mining algorithms are based on approximations. In earlier work, mining frequent items in a stream under the max-frequency measure proved to be effective for items. In this paper, we extended our work from items to itemsets. Firstly, an optimized incremental algorithm for mining frequent itemsets in a stream is presented. The algorithm maintains a very compact summary...
A Graph-Oriented Object Database Model - Gyssens, Marc; Paredaens, Jan; Van Gucht, Dirk
A simple, graph-oriented database model, supporting object-identity, is presented. For this model, a transformation language based on elementary graph operations is defined. This transformation language is suitable for both querying and updates. It is shown that the transformation language supports both set-operations (except for the powerset operator) and recursive functions.
A Graph-Oriented Object Model for Database End-User Interfaces - Gyssens, Marc; Paredaens, Jan; Van Gucht, Dirk
The current database research trend is towards systems which can deal with advanced data applications that go beyond the data standard "enterprise" of "office" database application. This trend is reflected in the research on extension architectures and object-oriented databases. Along with this trend, the need for better and easier-to-use database and end-user interfaces has been stressed. Therefore, we propose a graph-based data model which shares many features with existing data models, but which better facilitates the rigorous study of graphical database end-user interfaces. Graphs have been an integral part of the database design process ever since the introduction of semantic...
On a hierarchy of classes for nested databases - Gyssens, Marc; Paredaens, Jan; Van Gucht, Dirk
The nested relational model is nowadays generally accepted as a valid alternative to the flat relational model of Codd, because of its greater ability to model the structure of the real world. Not all nested relations however correspond to representations of the real world. Therefore, a hierarchy of more restricted classes of nested relations was defined. For one such class, called hierarchical nested relations (HNR), we give a characterization in terms of closure properties with respect to algebraic operations. For the largest subclass, the normalization-lossless relations (NL), consisting of all relations obtainable from flat relations using restructing operators only, we...
A structural decomposition for hypergraphs - Cohen, David A.; Jeavons, Peter G.; Gyssens, Marc
Hypergraphs arise in a variety of applications and are commonly classified as cyclic or acyclic. In this paper we develop a more refined classification scheme for cyclic hypergraphs based on a natural decomposition strategy. The fundamental building blocks in our decompositions are subsets of edges known as k-hinges. For any hypergraph, a set of more than k of its edges is defined to be a k-hinge if all connected components of the hypergraph with respect to the set of edges meet the latter within at most k of its edges. A k-hinge tree is a set of minimal k-hinges that...