Show simple item record

dc.contributor.authorHovland, Dageng
dc.date.accessioned2009-12-04T07:49:29Z
dc.date.available2009-12-04T07:49:29Z
dc.date.issued2009eng
dc.PublishedIn: Leucker, M.; Morgan, C. (eds.), Theoretical Aspects of Computing - ICTAC 2009: 231-245en
dc.identifier.urihttps://hdl.handle.net/1956/3628
dc.descriptionProceedings from the 6th International Colloquium Kuala Lumpur, Malaysia, August 16-20, 2009en
dc.description.abstractRegular expressions with numerical constraints are an extension of regular expressions, allowing to bound numerically the number of times that a subexpression should be matched. Expressions in this extension describe the same languages as the usual regular expressions, but are exponentially more succinct. We de ne a class of nite automata with counters and a deterministic subclass of these. Deterministic nite automata with counters can rec- ognize words in linear time. Furthermore, we describe a subclass of the regular expressions with numerical constraints, a polynomial-time test for this subclass, and a polynomial-time construction of deterministic nite automata with counters from expressions in the subclass.en_US
dc.language.isoengeng
dc.publisherSpringeren_US
dc.relation.ispartofseriesLecture Notes in Computer Scienceen
dc.relation.ispartofseries5684en
dc.titleRegular Expressions with Numerical Constraints and Automata with Countersen_US
dc.typeChapter
dc.typePeer reviewed
dc.description.versionAccepted versionen_US
dc.rights.holderSpringer-Verlagen_US
dc.identifier.doihttps://doi.org/10.1007/978-3-642-03466-4_15
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Teoretisk databehandling, programmeringsspråk og -teori: 421nob


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record