In this paper we present an extension of regular languages to support graph queries. The proposed extension is based on the introduc- Tion of a partial order on the strings of the languages. We extend regular expressions, regular grammars and finite state automata by introducing partial orders on strings, production rules and transitions, respectively. The relation among regular expressions, regular grammars and finite state automata is analyzed. We show how partially ordered languages can be used to define path queries to search graph databases and pre- sent 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.;GRECO, Sergio
1999-01-01
Abstract
In this paper we present an extension of regular languages to support graph queries. The proposed extension is based on the introduc- Tion of a partial order on the strings of the languages. We extend regular expressions, regular grammars and finite state automata by introducing partial orders on strings, production rules and transitions, respectively. The relation among regular expressions, regular grammars and finite state automata is analyzed. We show how partially ordered languages can be used to define path queries to search graph databases and pre- sent results on their computational complexity. Finally, we present an application of partially ordered languages for searching the Web.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
