12
Views
1
CrossRef citations to date
0
Altmetric
Original Articles

Equations and regular-like expressions for afa

Pages 157-172 | Received 11 May 1993, Published online: 19 Mar 2007
 

Abstract

lternating finite automata are a generalization of non-deterministic finite automata and a mechanism that models parallel computation. It has been shown in [6] that alternating finite automata (AFA) have several theoretical properties and practical features. In this paper, we further study alternating finite automata. A new type of system of equations is introduced. The systems of equations to be considered involve Boolean expressions over a finite set X and the symbols of an alphabet A. Each AFA can be described as a system of equations that has a unique fixpoint, and whose solutions are precisely the regular languages. We present an algebraic interpretation of AFA, which parallels that of regular expressions and of linear equations. We also explore direct ways of solving such systems and generating equivalent AFA from regular expressions or even extended regular expressions.

C.R Categories:

Present Address:Faculty of Science,Department of Mathematics and Computer Science U.A.E University, Al-Ain ,United Arab Emirates,*

Present Address:Faculty of Science,Department of Mathematics and Computer Science U.A.E University, Al-Ain ,United Arab Emirates,*

Notes

Present Address:Faculty of Science,Department of Mathematics and Computer Science U.A.E University, Al-Ain ,United Arab Emirates,*

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.