1,721,119 research outputs found
Preface
No full textThe FoIKS symposia provide a biennial forum for presenting and discussing theoretical and applied research on information and knowledge systems. The goal is to bring together researchers with an interest in this subject, share research experiences , promote collaboration, and identify new issues and directions for future research. Another characteristic of the FoIKS symposia is that they are a forum for intensive discussions. Speakers are given ample time to present their results, expound relevant background information, and put their research into context. Furthermore, participants are asked in advance to prepare a first response to a contribution of another author in order to initiate discussion. FoIKS 2016 solicited original contributions on foundational aspects of information and knowledge systems. This included submissions that apply ideas, theories or methods from specific disciplines to information and knowledge systems. Examples of such disciplines are discrete mathematics, logic and algebra, model theory, information theory, complexity theory, algorithmics and computation, statistics, and optimization
Database Dependencies
No full textFor a relational database to be valid, it is not sufficient that the various tables of which it is composed conform to the database schema. In addition, the instance must also conform to the intended meaning of the database. While many aspects of this intended meaning are inherently informal, it will generally induce certain formalizable relationships between the data in the database, in the sense that whenever a certain pattern is present among the data, this pattern can either be extended or certain data values must be equal. Such a relationship is called a database dependency
Typechecking top-down XML transformations: Fixed input or output schemas
No full textAbstractTypechecking 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
On matrices and K-relations
No full textWe show that the matrix query language 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 2. We then proceed to show that MATLANG can express all matrix queries expressible in the positive relational algebra on K-relations, when intermediate arities are restricted to 3. 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.We thank Floris Geerts for inspiring discussions. We also thank the anonymous reviewers for their comments which were very helpful in improving this paper
On matrices and K-relations
No full textWe show that the matrix query language 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 MATLANG can express all matrix queries expressible in the positive re-lational 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
The Complexity of Non-Iterated Probabilistic Justification Logic
No full textThe logic PJ is a probabilistic logic defined by adding (noniterated) probability operators to the basic justification logic J. In this paper we establish upper and lower bounds for the complexity of the derivability problem in the logic PJ. The main result of the paper is that the complexity of the derivability problem in PJ remains the same as the complexity of the derivability problem in the underlying logic J, which is π[p/2] -complete. This implies that the probability operators do not increase the complexity of the logic, although they arguably enrich the expressiveness of the language
- …
