### Les tests et leur caractérisation syntaxique

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

Back to Simple Search
# Advanced Search

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 ( computing all nodes satisfying a formula in a given structure) has 1. quadratic data complexity...

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 [16]. 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...

Given two trees (a target and a pattern ) and a natural number , consist in deciding whether occurs as an embedded subtree of and/or finding the number of size (at most) windows of which contain pattern as an embedded subtree. is an embedded subtree of if can be obtained by deleting some nodes from (if a node is deleted, all edges adjacent to are also deleted, and outgoing edges are replaced by edges going from the parent of (if it exists) to the children of ). Deciding whether ...

**Page 1**