| dc.contributor.author | Hovland, Dag | eng |
| dc.date.accessioned | 2009-12-04T07:49:29Z | |
| dc.date.available | 2009-12-04T07:49:29Z | |
| dc.date.issued | 2009 | eng |
| dc.Published | In: Leucker, M.; Morgan, C. (eds.), Theoretical Aspects of Computing - ICTAC 2009: 231-245 | en |
| dc.identifier.uri | https://hdl.handle.net/1956/3628 | |
| dc.description | Proceedings from the 6th International Colloquium Kuala Lumpur, Malaysia, August 16-20, 2009 | en |
| dc.description.abstract | Regular 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.iso | eng | eng |
| dc.publisher | Springer | en_US |
| dc.relation.ispartofseries | Lecture Notes in Computer Science | en |
| dc.relation.ispartofseries | 5684 | en |
| dc.title | Regular Expressions with Numerical Constraints and Automata with Counters | en_US |
| dc.type | Chapter | |
| dc.type | Peer reviewed | |
| dc.description.version | Accepted version | en_US |
| dc.rights.holder | Springer-Verlag | en_US |
| dc.identifier.doi | https://doi.org/10.1007/978-3-642-03466-4_15 | |
| dc.subject.nsi | VDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Teoretisk databehandling, programmeringsspråk og -teori: 421 | nob |
