The search session has expired. Please query the service again.
Inf-Datalog
extends the usual least fixpoint semantics of Datalog with greatest
fixpoint semantics: we defined inf-Datalog and characterized the
expressive power of various fragments of inf-Datalog in [CITE].
In the present paper, we study the
complexity of query evaluation on finite models
for (various fragments of) inf-Datalog.
We deduce a unified and elementary proof that global model-checking
(i.e. computing all nodes satisfying a formula in a given structure) has
1. quadratic data complexity...
The paper considers an algebraic notion of automorphic equivalence of models and of multi-models. It is applied to the solution of the problem of informational equivalence of knowledge bases. We show that in the case of linear subjects of knowledge the problem can be reduced to the well-known in computational group theory problems about isomorphism and conjugacy of subgroups of a general linear group.
In this paper we introduce a model to represent high-level semantic concepts that can be perceived in images. The concepts are learned and represented by means of a set of association rules that relate the presence of perceptual features to the fulfillment of a concept for a set of images. Since both the set of images where a perceptual feature appears and the set of images fulfilling a given concept are fuzzy, we use in fact fuzzy association rules for the learning model. The concepts so acquired...
This paper surveys research in the field of data mining, which
is related to discovering the dependencies between attributes in databases.
We consider a number of approaches to finding the distribution intervals of
association rules, to discovering branching dependencies between a given set
of attributes and a given attribute in a database relation, to finding fractional
dependencies between a given set of attributes and a given attribute in a
database relation, and to collaborative filtering.
In the XML standard, data are represented as unranked labeled
ordered trees. Regular unranked tree automata provide a useful
formalism for the validation of schemas enforcing regular structural
constraints on XML documents. However some concrete application
contexts need the expression of more general constraints than the
regular ones. In this paper we propose a new framework in which
context-free style structural constraints can be expressed and
validated. This framework is characterized by: (i)...
We prove the undecidability of Core XPath 1.0 (CXP) [G. Gottlob and C. Koch, in Proc. of 17th Ann. IEEE Symp. on Logic in Computer Science, LICS ’02 (Copenhagen, July 2002). IEEE CS Press (2002) 189–202.] extended with an Inflationary Fixed Point (IFP) operator. More specifically, we prove that the satisfiability problem of this language is undecidable. In fact, the fragment of CXP+IFP containing only the self and descendant axes is already undecidable.
In the relational model of databases a database state is thought of as a finite collection of relations between elements. For many applications it is convenient to pre-fix an infinite domain where the finite relations are going to be defined. Often, we also fix a set of domain functions and/or relations. These functions/relations are infinite by their nature. Some special problems arise if we use such an approach. In the paper we discuss some of the problems. We show that there exists a recursive...
Currently displaying 41 –
60 of
81