Simple-regular expressions and languages

Yo Sub Han; Gerhard Trippen; Derick Wood

Simple-regular expressions and languages

Yo Sub Han, Gerhard Trippen, Derick Wood

College of Computing

Research output: Contribution to conference › Paper › peer-review

Abstract

We define simple-regular expressions and languages. Simple-regular languages provide a necessary condition for a language to be outfix-free. We design algorithms that compute simple-regular languages from finite-state automata. Furthermore, we investigate the complexity blowup from a given finite-state automaton to its simple-regular language automaton and show that there is an exponential blowup. In addition, we present a finite-state automata construction for simple-regular expressions based on state expansion.

Original language	English
Pages	146-157
Number of pages	12
Publication status	Published - 2005
Event	7th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2005 - Como, Italy Duration: 2005 Jun 30 → 2005 Jul 2

Other

Other	7th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2005
Country/Territory	Italy
City	Como
Period	05/6/30 → 05/7/2

All Science Journal Classification (ASJC) codes

Software

Cite this

@conference{66587198f0b14c7384060f0e93775b8b,

title = "Simple-regular expressions and languages",

abstract = "We define simple-regular expressions and languages. Simple-regular languages provide a necessary condition for a language to be outfix-free. We design algorithms that compute simple-regular languages from finite-state automata. Furthermore, we investigate the complexity blowup from a given finite-state automaton to its simple-regular language automaton and show that there is an exponential blowup. In addition, we present a finite-state automata construction for simple-regular expressions based on state expansion.",

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

year = "2005",

language = "English",

pages = "146--157",

note = "7th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2005 ; Conference date: 30-06-2005 Through 02-07-2005",

}

TY - CONF

T1 - Simple-regular expressions and languages

AU - Han, Yo Sub

AU - Trippen, Gerhard

AU - Wood, Derick

PY - 2005

Y1 - 2005

N2 - We define simple-regular expressions and languages. Simple-regular languages provide a necessary condition for a language to be outfix-free. We design algorithms that compute simple-regular languages from finite-state automata. Furthermore, we investigate the complexity blowup from a given finite-state automaton to its simple-regular language automaton and show that there is an exponential blowup. In addition, we present a finite-state automata construction for simple-regular expressions based on state expansion.

AB - We define simple-regular expressions and languages. Simple-regular languages provide a necessary condition for a language to be outfix-free. We design algorithms that compute simple-regular languages from finite-state automata. Furthermore, we investigate the complexity blowup from a given finite-state automaton to its simple-regular language automaton and show that there is an exponential blowup. In addition, we present a finite-state automata construction for simple-regular expressions based on state expansion.

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

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

M3 - Paper

AN - SCOPUS:33646419678

SP - 146

EP - 157

T2 - 7th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2005

Y2 - 30 June 2005 through 2 July 2005

ER -

Simple-regular expressions and languages

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this