Vis enkel innførsel

dc.contributor.authorHovland, Dageng
dc.date.accessioned2010-05-20T12:51:00Z
dc.date.available2010-05-20T12:51:00Z
dc.date.issued2010eng
dc.PublishedIn: Dediu, A.-H.; Fernau, H.; Martín-Vide, C. (eds.), Language and Automata Theory and Applications - LATA 2010: 309-320en
dc.identifier.isbn978-3-642-13088-5en_US
dc.identifier.urihttps://hdl.handle.net/1956/3956
dc.descriptionProceedings from the 4th International Conference, LATA 2010 Trier, Germany, May 24-28, 2010en
dc.description.abstractThis 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.en_US
dc.language.isoengeng
dc.publisherSpringeren_US
dc.relation.ispartofseriesLecture Notes in Computer Scienceen
dc.relation.ispartofseries6031en
dc.titleThe Inclusion Problem for Regular Expressionsen_US
dc.typeChapter
dc.typePeer reviewed
dc.description.versionAccepted versionen_US
dc.rights.holderSpringer-Verlagen_US
dc.rights.holderCopyright 2010 Springer-Verlag. All rights reserved.en_US
dc.identifier.doihttps://doi.org/10.1007/978-3-642-13089-2_26
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Teoretisk databehandling, programmeringsspråk og -teori: 421nob


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel