Outfix-free regular languages and prime outfix-free decomposition

Yo Sub Han; Derick Wood

doi:10.1007/11560647_6

Outfix-free regular languages and prime outfix-free decomposition

Yo Sub Han, Derick Wood

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Citations (Scopus)

Abstract

A string x is an outfix of a string y if there is a string w such that x ₁wx ₂ = y, where x = x ₁x ₂ and a set X of strings is outfix-free if no string in X is an outfix of any other string in X. We examine the outfix-free regular languages. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines the outfix-freeness of regular languages. We consider two cases: A language is given as a set of strings and a language is given by an acyclic deterministic finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfix-free regular languages and design a linear-time prime outfix-free decomposition algorithm for outfix-free regular languages. We demonstrate the uniqueness of prime outfix-free decomposition.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages	96-109
Number of pages	14
DOIs	https://doi.org/10.1007/11560647_6
Publication status	Published - 2005
Event	2nd International Colloquium on Theoretical Aspects of Computing - ICTAC 2005 - Hanoi, Viet Nam Duration: 2005 Oct 17 → 2005 Oct 21

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3722 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	2nd International Colloquium on Theoretical Aspects of Computing - ICTAC 2005
Country/Territory	Viet Nam
City	Hanoi
Period	05/10/17 → 05/10/21

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/11560647_6

Cite this

Han, Y. S., & Wood, D. (2005). Outfix-free regular languages and prime outfix-free decomposition. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 96-109). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3722 LNCS). https://doi.org/10.1007/11560647_6

Han, Yo Sub ; Wood, Derick. / Outfix-free regular languages and prime outfix-free decomposition. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2005. pp. 96-109 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c970c34367074a8da1511f7fb2b7a383,

title = "Outfix-free regular languages and prime outfix-free decomposition",

abstract = "A string x is an outfix of a string y if there is a string w such that x 1wx 2 = y, where x = x 1x 2 and a set X of strings is outfix-free if no string in X is an outfix of any other string in X. We examine the outfix-free regular languages. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines the outfix-freeness of regular languages. We consider two cases: A language is given as a set of strings and a language is given by an acyclic deterministic finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfix-free regular languages and design a linear-time prime outfix-free decomposition algorithm for outfix-free regular languages. We demonstrate the uniqueness of prime outfix-free decomposition.",

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

year = "2005",

doi = "10.1007/11560647_6",

language = "English",

isbn = "3540291075",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "96--109",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

note = "2nd International Colloquium on Theoretical Aspects of Computing - ICTAC 2005 ; Conference date: 17-10-2005 Through 21-10-2005",

}

Han, YS & Wood, D 2005, Outfix-free regular languages and prime outfix-free decomposition. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3722 LNCS, pp. 96-109, 2nd International Colloquium on Theoretical Aspects of Computing - ICTAC 2005, Hanoi, Viet Nam, 05/10/17. https://doi.org/10.1007/11560647_6

Outfix-free regular languages and prime outfix-free decomposition. / Han, Yo Sub; Wood, Derick.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2005. p. 96-109 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3722 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Outfix-free regular languages and prime outfix-free decomposition

AU - Han, Yo Sub

AU - Wood, Derick

PY - 2005

Y1 - 2005

N2 - A string x is an outfix of a string y if there is a string w such that x 1wx 2 = y, where x = x 1x 2 and a set X of strings is outfix-free if no string in X is an outfix of any other string in X. We examine the outfix-free regular languages. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines the outfix-freeness of regular languages. We consider two cases: A language is given as a set of strings and a language is given by an acyclic deterministic finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfix-free regular languages and design a linear-time prime outfix-free decomposition algorithm for outfix-free regular languages. We demonstrate the uniqueness of prime outfix-free decomposition.

AB - A string x is an outfix of a string y if there is a string w such that x 1wx 2 = y, where x = x 1x 2 and a set X of strings is outfix-free if no string in X is an outfix of any other string in X. We examine the outfix-free regular languages. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines the outfix-freeness of regular languages. We consider two cases: A language is given as a set of strings and a language is given by an acyclic deterministic finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfix-free regular languages and design a linear-time prime outfix-free decomposition algorithm for outfix-free regular languages. We demonstrate the uniqueness of prime outfix-free decomposition.

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

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

U2 - 10.1007/11560647_6

DO - 10.1007/11560647_6

M3 - Conference contribution

AN - SCOPUS:33646389805

SN - 3540291075

SN - 9783540291077

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 96

EP - 109

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 2nd International Colloquium on Theoretical Aspects of Computing - ICTAC 2005

Y2 - 17 October 2005 through 21 October 2005

ER -

Han YS, Wood D. Outfix-free regular languages and prime outfix-free decomposition. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2005. p. 96-109. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11560647_6

Outfix-free regular languages and prime outfix-free decomposition

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this