www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/9900

Title: Regular Expressions with Counting: Weak versus Strong Determinism
Authors: GELADE, Wouter
GYSSENS, Marc
Martens, Wim
Issue Date: 2009
Publisher: SPRINGER-VERLAG BERLIN
Citation: Kralovic, R; Niwinski, D (Ed.) MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2009. p. 369-381.
Series/Report: Lecture Notes in Computer Science, 5734
Abstract: We study deterministic regular expressions extended with the counting operator. There exist two notions of determinism, strong and weak determinism, which almost coincide for standard regular expressions. This, however, changes dramatically in the presence of counting. In particular, we show that weakly deterministic expressions with counting are exponentially more succinct and strictly more expressive than strongly deterministic ones, even though they still do not capture all regular languages. In addition, we present a finite automaton model with counters, study its properties and investigate the natural extension of the Glushkov construction translating expressions with counting into such counting automata. This translation yields a deterministic automation if and only if the expression is strongly deterministic. These results then also allow to derive upper bounds for decision problems for strongly deterministic expressions with counting.
Notes: [Gelade, Wouter; Gyssens, Marc] Hasselt Univ, Hasselt, Belgium.
URI: http://hdl.handle.net/1942/9900
ISI #: 000269937800029
ISBN: 978-3-642-03815-0
ISSN: 0302-9743
Category: C1
Type: Proceedings Paper
Validation: ecoom, 2010
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A450.85 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.