Regular path queries under approximate semantics

DOI10.1007/s10472-005-9016-8zbMath1110.68033MaRDI QIDQ2502162

Gösta Grahne, Alex Thomo

Publication date: 12 September 2006

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-005-9016-8

zbMATH Keywords

semistructured data; transducers; weighted automata; regular path queries; approximate answers

Mathematics Subject Classification ID

68P15: Database theory

68Q45: Formal languages and automata

68Q55: Semantics in the theory of computing

Related Items

Visibly Pushdown Transducers for Approximate Validation of Streaming XML, Approximate XML structure validation based on document-grammar tree similarity, Evolving schemas for streaming XML, Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring, Fault-tolerant computation of distributed regular path queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rewriting of regular expressions and regular path queries
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• Improved limitedness theorems on finite automata with distance functions
• Limitedness theorem on finite automata with distance functions
• Rational equivalence relations
• On the equivalence, containment, and covering problems for the regular and context-free languages
• Regular path queries with constraints
• New upper bounds to the limitedness of distance automata
• Path constraints in semistructured databases
• On semigroups of matrices over the tropical semiring
• Finding Regular Simple Paths in Graph Databases