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.
Partially Ordered Regular Languages for Graph Queries
FLESCA S. G.;GRECO, Sergio
2005-01-01
Abstract
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
