Automata for XML -- a survey
From MaRDI portal
Publication:878749
DOI10.1016/j.jcss.2006.10.003zbMath1115.68101OpenAlexW2092398161MaRDI QIDQ878749
Publication date: 26 April 2007
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.2006.10.003
Related Items
Highly expressive query languages for unordered data trees ⋮ XML compression via directed acyclic graphs ⋮ State Complexity of Kleene-Star Operations on Trees ⋮ One-variable context-free hedge automata ⋮ State complexity of the concatenation of regular tree languages ⋮ On-the-fly bisimilarity checking for fresh-register automata ⋮ Unnamed Item ⋮ Learning Tree Languages ⋮ Synchronizing relations on words ⋮ Evolving schemas for streaming XML ⋮ Tree Automata with Global Constraints ⋮ XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles ⋮ Polynomial-time equivalence testing for deterministic fresh-register automata ⋮ Leafy automata for higher-order concurrency ⋮ On characterization of fuzzy tree pushdown automata ⋮ TREE AUTOMATA WITH GLOBAL CONSTRAINTS ⋮ Reasoning about XML with temporal logics and automata ⋮ Operational state complexity of nested word automata ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Rewriting of visibly pushdown languages for XML data integration ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Constant-time tree traversal and subtree equality check for grammar-compressed trees ⋮ State Trade-Offs in Unranked Tree Automata ⋮ Lattice-valued tree pushdown automata: pumping lemma and closure properties ⋮ Efficient inclusion checking for deterministic tree automata and XML schemas ⋮ Parameterized complexity of basic decision problems for tree automata ⋮ Regular expressions for data words
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- XML queries and constraints, containment and reformulation
- Frontiers of tractability for typechecking simple XML transformations
- Tree transducers, L systems, and two-way machines
- On two-way tree automata
- Finite-memory automata
- Typechecking for XML transformers
- An algebraic approach to data languages and timed languages
- On the power of tree-walking automata.
- XML with data values: Typechecking revisited.
- A comparison of pebble tree transducers with macro tree transducers
- A formal model for an expressive fragment of XSLT
- Query automata over finite trees
- Attribute grammars for unranked trees as a query language for structured documents
- The complexity of first-order and monadic second-order logic revisited
- Tree acceptors and some of their applications
- THE REGULARITY OF TWO-WAY NONDETERMINISTIC TREE AUTOMATA LANGUAGES
- Regular expression pattern matching for XML
- Expressiveness of structured document query languages based on attribute grammars
- THE ABSTRACT THEORY OF AUTOMATA
- Deciding Equivalence of Finite Tree Automata
- The complexity of XPath query evaluation and XML typing
- Conjunctive queries over trees
- Visibly pushdown languages
- Tree-walking automata do not recognize all regular languages
- Parallel and two-way automata on directed ordered acyclic graphs
- Minimal Ascending and Descending Tree Automata
- Macro Tree Translations of Linear Size Increase are MSO Definable
- Automated Reasoning with Analytic Tableaux and Related Methods
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Typechecking XML views of relational databases
- Finite state machines for strings over infinite alphabets
- Computer Science Logic
- Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
- Mathematical Foundations of Computer Science 2004
- Mathematical Foundations of Computer Science 2004
- CONCUR 2004 - Concurrency Theory
- Database Theory - ICDT 2005
- Database Theory - ICDT 2005
- Automata, Languages and Programming
- Automata, Languages and Programming
- Fundamentals of Computation Theory
- Database Programming Languages
- Containment and equivalence for a fragment of XPath
- Monadic datalog and the expressive power of languages for Web information extraction
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Translations on a context free grammar
- STACS 2005
- Developments in Language Theory
- Automata, Languages and Programming
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Rewriting Techniques and Applications
- One-unambiguous regular languages