Finding regular paths in acyclic graphs

dc.contributor.author	Wood, PT
dc.date.accessioned	2018-05-18T00:57:46Z
dc.date.available	2018-05-18T00:57:46Z
dc.date.issued	1990
dc.identifier		en
dc.identifier.citation	Wood PT (1990) Finding regular paths in acyclic graphs. South African Computer Journal Number 1, 1990	en
dc.identifier.issn	2313-7835
dc.identifier.uri	http://hdl.handle.net/10500/23924
dc.description.abstract	Increasing the expressive power of relational query languages by providing some form of recursion is currently a topic of much research. For many recursive queries in relational databases, a relation can be represented as labelled directed graph G, while the query can be viewed as finding simple paths in G that satisfy a given regular expression. Based on such a query language, it has been shown recently that, in this context, the general query evaluation problem on cyclic graphs is intractable. In this paper, we present an efficient algorithm for the case in which the graphs are acyclic.	en
dc.language.iso	en	en
dc.publisher	South African Institute of Computer Scientists and Information Technologists	en
dc.subject	Algorithms	en
dc.subject	Graph databases	en
dc.subject	Finite state automata	en
dc.subject	Query processing	en
dc.subject	Regular expressions	en
dc.title	Finding regular paths in acyclic graphs	en
dc.type	Article	en
dc.description.department	School of Computing	en