The generalization of generalized automata: Expression automata

Yo Sub Han, Derick Wood

Research output: Contribution to journalConference articlepeer-review

11 Citations (Scopus)


We explore expression automata with respect to determinism, minimization and primeness. 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 define the minimization of deterministic expression automata. Lastly, we discuss prime prefix-free regular languages. Note that we have omitted almost all proofs in this preliminary version.

Original languageEnglish
Pages (from-to)156-166
Number of pages11
JournalLecture Notes in Computer Science
Publication statusPublished - 2005
Event9th International Conference on Implementation and Application of Automata, CIAA 2004 - Kingston, Canada
Duration: 2004 Jul 222004 Jul 24

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'The generalization of generalized automata: Expression automata'. Together they form a unique fingerprint.

Cite this