<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

The inclusion problem for regular expressions

Name: The inclusion problem for regular expressions
Creator: Hovland, Dag
Keywords: Inclusion, Computer Networks and Communications, Applied Mathematics, programmeringsspråk og -teori: 421, 0102 computer and information sciences, 02 engineering and technology, Regular expressions, 01 natural sciences, 1-unambiguity, 004

descriptionPublicationkeyboard_double_arrow_right Article , Part of book or chapter of book 01 Jan 2010 Norway Publisher:Elsevier BVJournal:Journal of Computer and System Sciences, volume 78, pages 1,795-1,813 (issn: 0022-0000,

Authors: Hovland, Dag;

doi: 10.1016/j.jcss.2011.12.003 , 10.1007/978-3-642-13089-2_26

handle: 10852/9053 , 1956/3956

The inclusion problem for regular expressions

- Summary
- Subjects
- Metrics

Abstract

AbstractThis paper presents a polynomial-time algorithm for the inclusion problem for a large class 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 irrelevant parts of the right-hand expression. The irrelevant parts of 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. If the 1-ambiguity of the right-hand expression becomes a problem, the algorithm will report this. Otherwise, it will decide the inclusion problem for the input.

Country

Norway

Related Organizations

University of Bergen
Norway
University of Oslo
Norway

Keywords

Inclusion, Computer Networks and Communications, Applied Mathematics, programmeringsspråk og -teori: 421, Regular expressions, 1-unambiguity, 004, Theoretical Computer Science, :Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Teoretisk databehandling, programmeringsspråk og -teori: 421 [VDP], Formal languages, VDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Teoretisk databehandling, Computational Theory and Mathematics, VDP::420

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	17
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average