dc.contributor.author | Hovland, Dag | eng |
dc.date.accessioned | 2010-05-20T12:51:00Z | |
dc.date.available | 2010-05-20T12:51:00Z | |
dc.date.issued | 2010 | eng |
dc.Published | In: Dediu, A.-H.; Fernau, H.; Martín-Vide, C. (eds.), Language and Automata Theory and Applications - LATA 2010: 309-320 | en |
dc.identifier.isbn | 978-3-642-13088-5 | en_US |
dc.identifier.uri | https://hdl.handle.net/1956/3956 | |
dc.description | Proceedings from the 4th International Conference, LATA 2010 Trier, Germany, May 24-28, 2010 | en |
dc.description.abstract | 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. | en_US |
dc.language.iso | eng | eng |
dc.publisher | Springer | en_US |
dc.relation.ispartofseries | Lecture Notes in Computer Science | en |
dc.relation.ispartofseries | 6031 | en |
dc.title | The Inclusion Problem for Regular Expressions | en_US |
dc.type | Chapter | |
dc.type | Peer reviewed | |
dc.description.version | Accepted version | en_US |
dc.rights.holder | Springer-Verlag | en_US |
dc.rights.holder | Copyright 2010 Springer-Verlag. All rights reserved. | en_US |
dc.identifier.doi | https://doi.org/10.1007/978-3-642-13089-2_26 | |
dc.subject.nsi | VDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Teoretisk databehandling, programmeringsspråk og -teori: 421 | nob |