Regular languages with variables on graphs

DOI10.1016/j.ic.2011.10.010zbMath1279.68174OpenAlexW2021258113MaRDI QIDQ418127

Simone Santini

Publication date: 24 May 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2011.10.010

zbMATH Keywords

matchinggraphsregular expressionspaths in graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Matching regular expressions on uncertain data

Uses Software

• PERL
• Python
• XPath
• UnQL
• GraphLog

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Regular expressions with nested levels of back referencing form a hierarchy
• Time-space tradeoffs for undirected graph traversal by graph automata
• Pattern expressions and pattern automata
• On the equivalence, containment, and covering problems for the regular and context-free languages
• On the power of tree-walking automata.
• Weighted path queries on semistructured databases
• Parallel and two-way automata on directed ordered acyclic graphs
• Minimal Ascending and Descending Tree Automata
• Finding Regular Simple Paths in Graph Databases
• Database Theory - ICDT 2005
• Programming Techniques: Regular expression search algorithm
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS

This page was built for publication: Regular languages with variables on graphs