Show simple item record

dc.contributor.authorHovland, Dageng
dc.date.accessioned2010-05-20T12:51:00Z
dc.date.available2010-05-20T12:51:00Z
dc.date.issued2010eng
dc.identifier.citationIn: 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-5eng
dc.identifier.urihttp://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
dc.language.isoengeng
dc.publisherSpringereng
dc.relation.ispartofseriesLecture Notes in Computer Scienceen
dc.relation.ispartofseries6031en
dc.titleThe Inclusion Problem for Regular Expressionseng
dc.typePeer reviewedeng
dc.typeChaptereng
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Teoretisk databehandling, programmeringsspråk og -teori: 421nob
dc.rights.holderCopyright 2010 Springer-Verlag. All rights reserved.
dc.rights.holderSpringer-Verlageng
dc.type.versionAccepted versioneng
bora.peerreviewedPeer reviewedeng
bibo.doihttp://dx.doi.org/10.1007/978-3-642-13089-2_26eng
dc.identifier.doi10.1007/978-3-642-13089-2_26


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record