• norsk
    • English
  • norsk 
    • norsk
    • English
  • Logg inn
Vis innførsel 
  •   Hjem
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • Vis innførsel
  •   Hjem
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • Vis innførsel
JavaScript is disabled for your browser. Some features of this site may not work without it.

The Inclusion Problem for Regular Expressions

Hovland, Dag
Chapter, Peer reviewed
Accepted version
Thumbnail
Åpne
Accepted version (183.3Kb)
Permanent lenke
https://hdl.handle.net/1956/3956
Utgivelsesdato
2010
Metadata
Vis full innførsel
Samlinger
  • Department of Informatics [738]
Originalversjon
https://doi.org/10.1007/978-3-642-13089-2_26
Sammendrag
This paper presents a new polynomial-time algorithm for the inclusion problem for certain pairs of regular expressions. The algorithm is not based on construction of finite automata, and can therefore be faster than the lower bound implied by the Myhill-Nerode theorem. The algorithm automatically discards unnecessary parts of the right-hand expression. In these cases the right-hand expression might even be 1- ambiguous. For example, if r is a regular expression such that any DFA recognizing r is very large, the algorithm can still, in time independent of r, decide that the language of ab is included in that of (a+r)b. The algorithm is based on a syntax-directed inference system. It takes arbitrary regular expressions as input, and if the 1-ambiguity of the right-hand expression becomes a problem, the algorithm will report this.
Beskrivelse
Proceedings from the 4th International Conference, LATA 2010 Trier, Germany, May 24-28, 2010
Utgiver
Springer
Serie
Lecture Notes in Computer Science
6031
Opphavsrett
Springer-Verlag
Copyright 2010 Springer-Verlag. All rights reserved.

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit
 

 

Bla i

Hele arkivetDelarkiv og samlingerUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifterDenne samlingenUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifter

Min side

Logg inn

Statistikk

Besøksstatistikk

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit