Entry Bruggemann-Klein:1993:REF from tcs1990.bib

Last update: Wed Sep 26 02:11:46 MDT 2018                Valid HTML 4.0!

Index sections

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