Technical Report CS0669

 TR#: CS0669 Class: CS Title: FINITE-STATE DATALOG AUTOMATA AND RELATIONAL LANGUAGES Authors: Y. Shemesh and N. Francez PDF Not Available Abstract: We define the new notion of a (finite-state) {\em Datalog automaton}, a device for finite-state recognition of {\em relational languages} by means of {\em unification transitions}. Words in such a language are formed by composing base relations, and have the general form \ $r_{i_{1}}(X_{j_{1}}, X_{k_{1}}) \cdots r_{i_{n}} (X_{j_{n}}, X_{k_{n}})$\ for some \ $n$. {\em Generation} of such languages by regarding Horn clauses as grammars has been considered before, but to the best of our knowledge, {\em recognizing} such languages by suitably-designed automata is a new approach. The main result presented is a {\em pumping lemma}, forming a necessary condition for finite-state recognizability. Some example results about such automata are given. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0669), rather than to the URL of the PDF files directly. The latter URLs may change without notice.