Partially ordered regular languages for graph queries

In this paper we present an extension of regular languages to support graph queries. The proposed extension is based on the introduction of a partial order on the strings of the languages. We extend regular expressions and regular grammars by introducing partial orders on strings and production rules, respectively. The relations between regular expressions and regular grammars are analyzed. We show how partially ordered languages can be used to define path queries to search graph databases and present results on their computational complexity. Finally, we present an application of partially ordered languages for searching the Web.