RWTH Aachen University
The study of graph structured data has received much attention lately, due to numerous applications in areas such as biological networks, social networks and the semantic Web. Graph databases are directed graphs in which the edges are labeled with symbols from a finite alphabet. In this paper, the authors introduce logic for such graphs in which the domain is the set of edges. They compare its expressiveness with the standard logic in which the domain the set of vertices. Furthermore, they introduce a robust model of computation for such logic, the so called graph pebble automata.