On the Count of Trees

Everardo Barcenas 1 Pierre Genevès 1 Nabil Layaïda 1 Alan Schmitt 2
1 WAM - Web, adaptation and multimedia
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 SARDES - System architecture for reflective distributed computing environments
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Regular tree grammars and regular path expressions constitute core constructs widely used in programming languages and type systems. Nevertheless, there has been little research so far on frameworks for reasoning about path expressions where node cardinality constraints occur along a path in a tree. We present a logic capable of expressing deep counting along paths which may include arbitrary recursive forward and backward navigation. The counting extensions can be seen as a generalization of graded modalities that count immediate successor nodes. While the combination of graded modalities, nominals, and inverse modalities yields undecidable logics over graphs, we show that these features can be combined in a decidable tree logic whose main features can be decided in exponential time. Our logic being closed under negation, it may be used to decide typical problems on XPath queries such as satisfiability, type checking with relation to regular types, containment, or equivalence.
Document type :
Reports
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/inria-00473160
Contributor : Everardo Barcenas <>
Submitted on : Tuesday, August 24, 2010 - 10:18:42 AM
Last modification on : Thursday, February 21, 2019 - 1:31:23 AM
Long-term archiving on : Thursday, November 25, 2010 - 2:23:43 AM

Files

RR-7251.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00473160, version 2
  • ARXIV : 1008.5073

Collections

Citation

Everardo Barcenas, Pierre Genevès, Nabil Layaïda, Alan Schmitt. On the Count of Trees. [Research Report] RR-7251, INRIA. 2010. ⟨inria-00473160v2⟩

Share

Metrics

Record views

1063

Files downloads

274