2010/05/31 by Everardo Barcenas, Everardo Bárcenas, Pierre Genevès +8
Computer Science · #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Natural Language Processing Techniques #Semantic Web and Ontologies #cs.LO
paper · pdf · doi:10.48550/arxiv.1005.5623
arxiv created 2010/05/31 · openalex publication_date 2010/05/31 · arxiv updated 2010/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 reasoning frameworks for 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 tree logic decidable in exponential time.