Entry Bruggemann-Klein:1993:REF from tcs1990.bib
Last update: Wed Sep 26 02:11:46 MDT 2018
Top |
Symbols |
Numbers |
Math |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z
BibTeX entry
@Article{Bruggemann-Klein:1993:REF,
author = "Anne Br{\"u}ggemann-Klein",
title = "Regular expressions into finite automata",
journal = j-THEOR-COMP-SCI,
volume = "120",
number = "2",
pages = "197--213",
day = "22",
month = nov,
year = "1993",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Mon Jul 19 22:17:43 MDT 1999",
bibsource = "http://www.elsevier.com/cgi-bin/cas/tree/store/tcs/cas_free/browse/browse.cgi?year=1993&volume=120&issue=2;
http://www.math.utah.edu/pub/tex/bib/tcs1990.bib",
URL = "http://www.elsevier.com/cgi-bin/cas/tree/store/tcs/cas_sub/browse/browse.cgi?year=1993&volume=120&issue=2&aid=1327",
abstract = "This paper shows that the Glushkov automaton can be
constructed in a time quadratic in the size of the
expression, and that this is worst-case optimal. For
deterministic expressions, his algorithm has even
linear run time. This improves on the cubic time
methods suggested in the literature (Book et al. 1971;
Aho et al. 1986; Berry and Sethi 1986). A major step of
the algorithm consists in bringing the expression into
what is called star normal form. This concept is also
useful for characterizing the relationship between two
types of unambiguity that have been studied in the
literature. Namely, the author shows that, modulo a
technical condition, an expression is strongly
unambiguous (Sippu and Soisalon-Soininen 1988) if and
only if it is weakly unambiguous (Book et al. 1971) and
in star-normal form. This leads to his third result, a
quadratic-time decision algorithm for weak unambiguity,
that improves on the biquadratic method introduced by
Book et al. (1971).",
acknowledgement = ack-nhfb,
affiliation = "Inst. fur Inf., Freiburg Univ., Germany",
classification = "C4210 (Formal logic); C4220 (Automata theory);
C6130D (Document processing techniques)",
corpsource = "Inst. fur Inf., Freiburg Univ., Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "Description language; description language;
deterministic regular expressions; Deterministic
regular expressions; Document processing; document
processing; Document types; document types;
E-transitions; finite automata; formal languages;
nondeterministic finite automaton; Nondeterministic
finite automaton; page description languages;
Quadratic-time decision algorithm; quadratic-time
decision algorithm; regular expressions; Regular
expressions; SGML standard; standards; star normal
form; Star normal form; textual markup systems; Textual
markup systems; Worst-case optimal; worst-case
optimal",
pubcountry = "Netherlands",
thesaurus = "Finite automata; Formal languages; Page description
languages; Standards",
treatment = "P Practical; T Theoretical or Mathematical",
}
Related entries
- author,
79(1)241
- automaton,
76(2)223,
78(2)363,
79(1)151,
84(2)281,
88(1)117,
88(2)231,
91(1)57,
92(1)119,
92(1)181,
92(2)249,
93(2)227,
95(1)159,
96(2)305,
97(2)233,
97(2)245,
98(2)347,
106(1)61,
108(1)83,
115(2)391,
116(2)305,
116(2)373,
119(2)233,
123(2)199,
125(2)243,
125(2)315,
131(2)295,
134(1)253,
134(2)387,
136(2)291
- case, worst-,
74(3)273,
84(1)127,
93(2)279,
100(1)185,
103(2)283,
117(1)187,
128(1)75,
129(2)397,
132(1)1
- characterizing,
100(1)45,
100(2)347
- concept,
70(1)159,
77(3)267,
86(2)377,
87(1)189,
90(1)253,
100(1)157,
120(1)45,
121(1)89,
133(2)387
- condition,
70(1)35,
70(1)151,
70(2)179,
72(1)27,
74(1)3,
75(1)111,
83(1)57,
83(2)189,
86(1)81,
86(2)233,
87(2)315,
88(2)269,
93(2)185,
93(2)227,
93(2)279,
94(1)101,
94(1)141,
94(2)335,
95(2)307,
97(1)143,
97(2)233,
100(1)157,
100(2)267,
100(2)325,
103(1)39,
105(1)7,
109(1)181,
110(1)1,
111(1)89,
112(1)145,
112(2)413,
113(1)93,
118(2)301,
120(1)69,
121(1)309,
126(2)183,
129(1)123,
131(2)271,
132(1)259
- cubic,
84(2)179,
109(1)83
- decision,
71(3)281,
72(1)39,
72(2)265,
74(1)71,
80(2)227,
81(1)137,
81(2)169,
82(1)19,
84(1)127,
84(2)199,
85(1)33,
93(2)279,
95(1)115,
98(1)137,
98(1)z,
106(2)351,
107(1)63,
110(2)419,
112(1)145,
112(2)371,
113(1)119,
118(2)193,
119(1)173,
123(2)183,
125(2)339,
126(2)183,
127(1)25,
128(1)179,
133(2)307,
134(2)329,
134(2)365,
134(2)387,
135(1)139
- description,
71(1)133,
76(2)223,
79(1)163,
90(1)171,
96(2)285,
104(2)285,
114(1)63,
117(1)255
- even,
88(1)59
- expression,
74(2)199,
74(3)273,
74(3)329,
75(1)85,
76(2)273,
77(1)97,
77(3)291,
78(1)113,
82(1)141,
82(2)403,
84(2)225,
85(2)283,
87(1)81,
88(2)351,
89(2)207,
91(1)101,
92(1)19,
96(2)285,
97(2)217,
107(2)209,
108(2)291,
116(1)33,
124(1)127,
127(2)287,
128(1)211,
134(1)27
- form,
73(2)231,
79(1)227,
81(2)305,
82(1)95,
83(2)219,
87(2)287,
92(1)87,
92(1)z,
93(1)91,
94(2)199,
95(2)339,
97(1)105,
97(2)233,
98(1)115,
102(2)307,
104(1)3,
107(2)253,
112(2)277,
116(1)59,
119(1)145,
121(1)71,
123(2)199,
133(2)387
- has,
112(2)311
- have,
87(1)81,
124(1)149
- method,
70(1)127,
71(2)z,
73(1)61,
74(1)95,
74(3)253,
79(1)241,
80(2)303,
81(2)189,
81(2)269,
82(2)215,
82(2)303,
84(2)225,
85(1)155,
85(1)205,
85(2)213,
86(2)343,
86(2)377,
88(1)15,
88(2)313,
89(1)63,
92(1)119,
93(1)91,
94(2)261,
95(2)207,
96(1)157,
98(1)137,
98(1)z,
103(2)283,
103(2)335,
104(1)89,
105(2)275,
106(1)3,
106(1)21,
113(2)259,
116(1)59,
116(2)291,
117(1)187,
117(1)z,
118(2)99,
118(2)193,
119(1)215,
119(1)z,
123(1)95,
123(1)131,
123(1)139,
123(2)291,
123(2)389,
125(1)61,
125(2)329,
125(2)345,
125(2)355,
126(2)143,
128(1)31,
128(1)99,
129(2)407,
131(1)1,
133(1)65,
133(1)165,
133(2)361,
133(2)421,
134(1)107,
135(2)319,
135(2)345,
136(1)57
- modulo,
74(3)325,
84(1)23,
86(2)143,
104(1)29,
112(1)53,
112(2)291,
134(1)175
- nondeterministic,
74(1)115,
74(2)217,
75(3)289,
77(3)221,
78(1)137,
81(2)317,
82(1)141,
82(2)389,
84(2)165,
85(1)53,
85(2)305,
88(1)1,
88(1)15,
88(1)99,
88(2)269,
88(2)297,
90(1)151,
91(2)129,
93(1)43,
97(2)183,
101(1)99,
101(2)161,
103(1)3,
106(2)351,
107(1)95,
107(2)305,
108(2)393,
115(2)225,
118(1)49,
118(1)67,
119(1)215,
120(1)123,
125(2)243,
125(2)295,
127(1)171,
129(2)323,
129(2)337,
132(1)319,
133(1)3,
133(2)341,
134(1)253,
134(2)545,
135(1)139
- normal,
79(1)227,
87(2)287,
94(2)199,
95(2)339,
97(1)105,
97(2)233,
104(1)3,
105(1)27,
107(2)277,
121(1)71,
129(1)167,
131(2)375
- only,
96(2)411
- optimal,
71(3)401,
74(1)95,
74(2)183,
76(1)93,
76(2)331,
77(3)291,
80(1)105,
81(2)257,
82(1)113,
82(1)157,
84(1)127,
84(2)179,
85(1)155,
86(2)365,
87(2)251,
92(1)33,
92(1)87,
92(1)z,
93(2)245,
106(2)361,
108(2)271,
111(1)191,
115(2)351,
119(2)355,
120(2)261,
123(2)377,
125(1)91,
127(2)395,
128(1)179,
129(2)323,
130(1)17,
132(1)403,
134(2)263,
134(2)559
- paper,
92(1)1,
119(2)323,
122(1)1,
141(1)329
- processing,
73(1)1,
73(1)61,
74(2)121,
74(2)183,
76(1)93,
76(1)115,
81(2)237,
89(1)179,
90(1)185,
91(2)285,
93(1)75,
95(1)1,
95(1)169,
96(1)3,
96(1)217,
102(2)253,
104(2)299,
108(2)371,
116(1)33,
116(1)59,
116(1)95,
116(1)117,
116(1)151,
116(1)195,
119(2)355,
128(1)127,
128(1)159,
128(1)211,
129(2)293,
129(2)397,
130(1)101,
133(2)267,
133(2)421,
134(2)287,
134(2)365
- quadratic,
81(2)257,
92(1)3,
92(2)319,
102(2)307,
132(1)291,
133(1)65,
133(1)85,
133(1)z
- regular,
70(2)213,
73(1)91,
73(3)329,
74(3)341,
75(1)157,
76(2)261,
76(2)273,
76(2)323,
77(1)97,
79(1)25,
81(2)305,
82(1)19,
83(2)287,
84(2)293,
85(1)117,
86(2)233,
87(1)43,
87(2)315,
88(1)139,
88(2)287,
88(2)351,
91(1)85,
91(1)101,
96(2)285,
97(2)217,
98(2)163,
99(1)79,
100(1)67,
101(1)133,
103(2)191,
103(2)409,
104(2)161,
106(1)61,
106(1)119,
108(1)17,
108(2)393,
112(2)187,
112(2)413,
115(2)261,
116(2)305,
116(2)373,
119(2)267,
124(2)329,
125(2)315,
125(2)361,
127(2)287,
129(1)187,
131(2)311,
131(2)463,
132(1)71,
133(1)49,
134(1)107,
134(1)119,
134(1)175,
134(1)189,
134(1)253,
134(2)537
- relationship,
81(1)117,
96(2)285,
103(2)365,
105(1)57,
106(2)243
- result,
70(1)85,
73(1)47,
73(3)249,
73(3)279,
79(1)111,
79(1)137,
80(2)289,
85(2)305,
87(1)203,
87(2)229,
87(2)287,
88(2)231,
91(2)129,
92(2)249,
93(2)265,
94(2)161,
95(1)115,
97(1)143,
99(1)1,
104(1)3,
110(1)145,
113(1)119,
116(1)195,
116(2)317,
121(1)71,
125(2)243,
128(1)3,
134(2)387,
135(2)361,
136(2)507
- run,
115(2)291
- size,
74(3)273,
78(2)357,
79(1)25,
81(2)237,
82(1)85,
84(2)225,
87(2)347,
88(1)117,
93(2)303,
96(2)305,
102(2)283,
107(1)95,
107(1)121,
116(1)195,
116(2)305,
127(2)351,
128(1)211,
129(2)397,
131(2)375
- standard,
82(2)373,
83(2)237,
96(1)73,
102(2)329,
108(1)151,
108(2)331,
117(1)187,
117(1)243,
117(1)255,
129(2)309,
129(2)407,
130(1)17
- star,
76(2)273,
79(1)3,
79(1)137,
88(2)351,
91(1)85,
97(2)217,
106(2)265,
106(2)327,
131(2)311,
132(1)71
- step,
77(1)27,
79(2)275
- strongly,
76(1)143,
84(2)281,
93(1)43,
94(1)101,
103(2)283,
110(2)419,
111(1)125,
122(1)201
- textual,
127(1)181
- two,
73(3)265,
74(3)329,
76(2)273,
79(1)241,
86(2)143,
92(1)77,
95(1)169,
95(2)323,
98(2)339,
100(1)105,
104(2)161,
112(2)311,
112(2)391,
123(2)239,
127(1)187,
131(2)361,
131(2)449,
134(2)415,
136(2)507
- unambiguity,
107(1)77
- unambiguous,
79(1)25,
81(2)311,
99(2)291,
107(1)77
- useful,
71(3)419,
98(1)65
- weak,
70(1)127,
79(2)295,
82(2)409,
83(2)323,
87(1)203,
87(1)221,
93(2)185,
93(2)227,
94(1)101,
97(2)233,
103(1)143,
112(2)413,
118(2)193,
133(1)3,
133(1)85
- weakly,
74(1)71,
82(2)409,
101(1)99,
113(1)119,
120(2)279
- worst-case,
74(3)273,
84(1)127,
93(2)279,
100(1)185,
103(2)283,
117(1)187,
128(1)75,
129(2)397,
132(1)1