|
Upper bounds on finite-automaton complexity for generalized regular expressions in a one-letter alphabet
Z. R. Dang
Abstract:
We compare the complexity of specifying a regular event by a finite automaton and a generalized regular expression. The measure of complexity of the automaton is the number of its states $G$, and the measure of complexity of the generalized regular expression is its refined length $\alpha$. We show that for generalized (having operations of set-theoretic complementation and intersection) regular expressions in a one-letter alphabet, $G\leqslant 3^\alpha$.
Received: 20.12.1988
Citation:
Z. R. Dang, “Upper bounds on finite-automaton complexity for generalized regular expressions in a one-letter alphabet”, Diskr. Mat., 1:4 (1989), 12–16
Linking options:
https://www.mathnet.ru/eng/dm936 https://www.mathnet.ru/eng/dm/v1/i4/p12
|
| Statistics & downloads: |
| Abstract page: | 379 | | Full-text PDF : | 164 | | References: | 2 | | First page: | 1 |
|