The generalization of generalized automata: Expression automata

Yo Sub Han; Derick Wood

doi:10.1007/978-3-540-30500-2_15

The generalization of generalized automata: Expression automata

Yo Sub Han, Derick Wood

College of Computing

Research output: Contribution to journal › Conference article › peer-review

11 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	156-166
Number of pages	11
Journal	Lecture Notes in Computer Science
Volume	3317
DOIs	https://doi.org/10.1007/978-3-540-30500-2_15
Publication status	Published - 2005
Event	9th International Conference on Implementation and Application of Automata, CIAA 2004 - Kingston, Canada Duration: 2004 Jul 22 → 2004 Jul 24

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-30500-2_15

Cite this

@article{ab9f06c9030a4f9888ac1be879c886e7,

title = "The generalization of generalized automata: Expression automata",

abstract = "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.",

author = "Han, {Yo Sub} and Derick Wood",

year = "2005",

doi = "10.1007/978-3-540-30500-2_15",

language = "English",

volume = "3317",

pages = "156--166",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Verlag",

note = "9th International Conference on Implementation and Application of Automata, CIAA 2004 ; Conference date: 22-07-2004 Through 24-07-2004",

}

TY - JOUR

T1 - The generalization of generalized automata

T2 - 9th International Conference on Implementation and Application of Automata, CIAA 2004

AU - Han, Yo Sub

AU - Wood, Derick

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=23944454840&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23944454840&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-30500-2_15

DO - 10.1007/978-3-540-30500-2_15

M3 - Conference article

AN - SCOPUS:23944454840

SN - 0302-9743

VL - 3317

SP - 156

EP - 166

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

Y2 - 22 July 2004 through 24 July 2004

ER -

The generalization of generalized automata: Expression automata

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this