Bibliographic Details
| Title: |
New finite automata corresponding to semiextended regular expressions. |
| Authors: |
Yamamoto, Hiroaki1 |
| Source: |
Systems & Computers in Japan. 9/1/2005, Vol. 36 Issue 10, p54-61. 8p. |
| Subjects: |
Sequential machine theory, Automation, Machine theory, Computers, Synchronization, Time measurements |
| Abstract: |
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 [ABSTRACT FROM AUTHOR] |
|
Copyright of Systems & Computers in Japan is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
