Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13185
Title: | Regular Expressions with Counting: Weak versus Strong Determinism | Authors: | GELADE, Wouter GYSSENS, Marc MARTENS, Wim |
Issue Date: | 2012 | Source: | SIAM JOURNAL ON COMPUTING, 41(1), p. 160-190 | 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 automaton 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. | Document URI: | http://hdl.handle.net/1942/13185 | ISSN: | 0097-5397 | e-ISSN: | 1095-7111 | DOI: | 10.1137/100814196 | ISI #: | 000300892300008 | Rights: | © 2012 Society for Industrial and Applied Mathematics | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2013 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Regular_Expressions_with_Counting_Paper.pdf | Non Peer-reviewed author version | 366.65 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
30
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
28
checked on Oct 13, 2024
Page view(s)
78
checked on Sep 7, 2022
Download(s)
282
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.