
Grimson, Rafael; Kuijpers, Bart; Othman, Walied
We introduce new firstorder languages for the elementary ndimensional geometry and elementary ndimensional 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 WILEYVCH Verlag GmbH & Co. KGaA, Weinheim

Goovaerts, Marc; Leinders, Dirk
In this paper, we evaluate the quality of the metadata of an OAIcompliant 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 machineunderstandability 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...

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...

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 wordinitial consonants is investigated. Several definitions of IF/FL and their components are computed using a longitudinal corpus of interactions between 30 Dutchspeaking 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 childdirected speech. Although IF and FL significantly correlate, they do have a different impact on the...

Gillis, Joris J.M.; Van den Bussche, Jan
This paper characterizes the expressive power of a subclass of firstorder logical decision trees (FOLDTs) as a fragment of firstorder logic. Specifically, using safe FOLDTs one can express precisely the boolean combinations of safe existential sentences.

Gelade, Wouter; Neven, Frank
Martens et al. defined a patternbased 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 typefree 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 singletype extended DTDs. The investigation is carried out relative to three...

Calders, Toon; Ramon, Jan; Van Dyck, Dries
In graph mining, a frequency measure for graphs is antimonotonic 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):243260, 2006) already gave sufficient and necessary conditions for antimonotonicity of graph measures depending only on the edgeoverlaps between the instances of the pattern in a labeled graph. We extend these results to homomorphisms, isomorphisms and homeomorphisms on both labeled and unlabeled,...

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 quantifierfree firstorder 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 contextfree language can be maintained in DYNFO and a number of specific contextfree languages, for example all Dycklanguages, are maintainable in DYNQF. Furthermore, the dynamic...

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 graphtheoretical characterization of the effect...

Leal Valentim, Felipe; Neven, Frank; Boyen, Peter; van Dijk, Aalt D. J.
The specificity of proteinprotein 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, largescale detection of protein interfaces remains a challenge. Here, we present a sequence and interactomebased approach to mine interaction motifs from the recently published Arabidopsis thaliana interactome. The resultant proteomewide predictions are available via www.ab.wur.nl/sliderbio and set the stage for further investigations of proteinprotein binding sites. To assess our method, we first show that, by using a...

Hellings, Jelle; Fletcher, George H. L.; Haverkort, Herman
In this paper we introduce the first efficient externalmemory 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,...

Brijder, Robert; Gillis, Joris J.M.; Van den Bussche, Jan
Recently we have introduced a formal graphbased 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 welltyped programs are well defi ned on all inputs adhering to given input types. The contribution of...

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 twigdefinable queries, we study the complexity of the problem to decide whether the query by a given NSTA is twigdefinable. In particular, we obtain that the latter problem is EXPTIMEcomplete. In addition, we show that it is also EXPTIMEcomplete to de cide whether the query by...

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, userfriendly frontend. 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 frontend 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...

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...

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 maxfrequency 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...

Gyssens, Marc; Paredaens, Jan; Van Gucht, Dirk
A simple, graphoriented database model, supporting objectidentity, 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 setoperations (except for the powerset operator) and recursive functions.

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 objectoriented databases. Along with this trend, the need for better and easiertouse database and enduser interfaces has been stressed. Therefore, we propose a graphbased data model which shares many features with existing data models, but which better facilitates the rigorous study of graphical database enduser interfaces. Graphs have been an integral part of the database design process ever since the introduction of semantic...

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 normalizationlossless relations (NL), consisting of all relations obtainable from flat relations using restructing operators only, we...

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 khinges. For any hypergraph, a set of more than k of its edges is defined to be a khinge 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 khinge tree is a set of minimal khinges that...