New finite automata corresponding to semiextended regular expressions

A semiextended regular expression is a regular expression having an intersection operation. It is known that a regular expression of length m can be transformed into a nondeterministic finite automaton of at most 2m states; however, if the semiextended regular expression is to be transformed into an NFA, the number of states will increase exponentially because of the intersection operation. In this paper, we propose a new model called a partially input-synchronized alternating finite automaton and show that a semiextended regular expression can be transformed into a partially input-synchronized alternating finite automaton of at most 2m states. Yamamoto applied this result to the membership problem of semiextended regular expressions. © 2005 Wiley Periodicals, Inc. Syst Comp Jpn, 36(10): 54–61, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10623