Attribute grammars for unranked trees as a query language for structured documents

DOI10.1016/j.jcss.2004.10.008zbMath1101.68636OpenAlexW2090623861MaRDI QIDQ1776378

Frank Neven

Publication date: 12 May 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.10.008

zbMATH Keywords

XMLComplexityMonadic second-order logicExpressivenessAttribute grammarsUnranked trees

Mathematics Subject Classification ID

Database theory (68P15) Grammars and rewriting systems (68Q42) Data structures (68P05)

Related Items (5)

Deciding twig-definability of node selecting tree automata ⋮ Automata for XML -- a survey ⋮ Translation of tree-processing programs into stream-processing programs based on ordered linear type ⋮ On the complexity of regular-grammars with integer attributes ⋮ Optimizing the region algebra is PSPACE-complete

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domains of partial attributed tree transducers
• Composition and evaluation of attribute coupled grammars
• Attribute grammars. Definitions, systems and bibliography
• Algebras for querying text regions: Expressive power and optimization
• Complexity results for two-way and multi-pebble automata and their logics
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• Query automata over finite trees
• Computer science today. Recent trends and developments
• Expressiveness of structured document query languages based on attribute grammars
• Weak Second‐Order Arithmetic and Finite Automata
• Deciding Equivalence of Finite Tree Automata
• Generalizations of regular sets and their application to a study of context-free languages
• The intrinsically exponential complexity of the circularity problem for attribute grammars
• A Grammar-Based Approach Towards Unifying Hierarchical Data Models
• Semantics of context-free languages
• Définition et etude des Bilangages réguliers
• Ambiguity in Graphs and Expressions
• One-unambiguous regular languages
• Normal form algorithms for extended context-free grammars

This page was built for publication: Attribute grammars for unranked trees as a query language for structured documents