| TR#: | CIS9111 |
| Class: | CIS |
| Title: | THE EXPRESSIVE POWER OF
TRANSITIVE CLOSURE AND 2-WAY MULTIHEAD AUTOMATA |
| Authors: | Y.Bargury and J. Makowsky |
| PostScript | Not Available |
| Abstract: | It is known, that over 1-dimensional strings, the expressive power of 2-way multihead (non) deterministic automata and (non) deterministic Transitive Closure formulas is (non) deterministic log space [IbCS073, Im88]. However, the subset of formulas needed to simulate exactly $k$ heads is unknown. It is also unknown if the automata and formulas have the same expressive power over more general structures such as multidimensional grids. We define a reduction from $k$-head automata to formulas of arity $k$, which works also for grids. The method used is a generalization of [Kl56], and the formulas obtained are a generalization of regular expressions to multihead automata and to grid languages. as simple applications, we use the reduction to show that the power of formulas of arity 1 over strings define (classical) regular languages, to give a simpler equivalent of the $L = NL$ open problem, and to establish the equivalence of the automata and formulas over grids. |
| 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/CIS/CIS9111), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.
To the list of the CIS technical reports of 1991
To the main CS technical reports page