Two Complete Axiom Systems for the Algebra of Regular Events
Author:
Open Access
- 1 January 1966
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 13 (1) , 158-169
Abstract
The theory of finite automata is closely linked with the theory of Kleene's regular expressions. In this paper, two formal systems for the algebraic transformation of regular expressions are developed. Both systems are consistent and complete; i.e., the set of equations derivable within the system equals the set of equations between two regular expressions denoting the same event. One of the systems is based upon the uniqueness of the solution of certain regular expression equations, whereas some facts concerning the representation theory of regular events are used in connection with the other.Keywords
This publication has 5 references indexed in Scilit:
- Derivatives of Regular ExpressionsJournal of the ACM, 1964
- Rules to Manipulate Regular Expressions of Finite AutomataIEEE Transactions on Electronic Computers, 1962
- Regular Expressions and State Graphs for AutomataIEEE Transactions on Electronic Computers, 1960
- Realization of Events by Logical NetsJournal of the ACM, 1958
- Representation of Events in Nerve Nets and Finite Automata1956