Wyniki wyszukiwania - BazTech

1

State Elimination Heuristics for Short Regular Expressions

Han Y-S.

Fundamenta Informaticae

|

2013

|

Vol. 128, nr 4

445--462

EN

State elimination is an intuitive and easy-to-implement algorithm that computes a regular expression from a finite-state automaton (FA). It is very hard to compute the shortest regular expression for a given FA in general and we cannot avoid the exponential blow-up. This implies that state elimination cannot avoid the exponential blow-up either. Nevertheless, since the size of a regular expression by state elimination depends on the state removal sequence, we can have a shorter regular expression if we choose a better removal sequence for state elimination. This observation motivates us to examine state elimination heuristics based on the structural properties of the input FA and implement state elimination using the heuristics that run in polynomial time. We demonstrate the effectiveness of our algorithm by experiment results.

2

Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages

Han Y-S., Salomaa K., Wood D.

Fundamenta Informaticae

|

2009

|

Vol. 90, nr 1-2

93-106

EN

We investigate the nondeterministic state complexity of basic operations for prefix-free regular languages. The nondeterministic state complexity of an operation is the number of states that are necessary and sufficient in the worst-case for a minimal nondeterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, union, intersection, Kleene star, reversal and complementation for prefix-free regular languages.

3

Outfix-Free Regular Languages and Prime Outfix-Free Decomposition

Han Y-S., Wood D.

Fundamenta Informaticae

|

2007

|

Vol. 81, nr 4

441-457

EN

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

4

Intercode Regular Languages

Han Y-S., Salomaa K., Wood D.

Fundamenta Informaticae

|

2007

|

Vol. 76, nr 1-2

113-128

EN

Intercodes are a generalization of comma-free codes. Using the structural properties of finite-state automata recognizing an intercode we develop a polynomial-time algorithm for determining whether or not a given regular language L is an intercode. If the answer is yes, our algorithm yields also the smallest index k such that L is a k-intercode. Furthermore, we examine the prime intercode decomposition of intercode regular languages and design an algorithm for the intercode primality test of an intercode recognized by a finite-state automaton. We also propose an algorithm that computes the prime intercode decomposition of an intercode regular language in polynomial time. Finally, we demonstrate that the prime intercode decomposition need not be unique.