THE GENERALIZATION OF GENERALIZED AUTOMATA: EXPRESSION AUTOMATA

We explore expression automata with respect to determinism and minimization. We define determinism of expression automata using prefix-freeness. This approach is, to some extent, similar to that of Giammarresi and Montalbano's definition of deterministic generalized automata. We prove that dete...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2005-06, Vol.16 (3), p.499-510
Main Authors: HAN, YO-SUB, WOOD, DERICK
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We explore expression automata with respect to determinism and minimization. We define determinism of expression automata using prefix-freeness. This approach is, to some extent, similar to that of Giammarresi and Montalbano's definition of deterministic generalized automata. We prove that deterministic expression automata languages are a proper subfamily of the regular languages. We close by defining the minimization of deterministic expression automata.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054105003121