Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/9900
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGELADE, Wouter-
dc.contributor.authorGYSSENS, Marc-
dc.contributor.authorMARTENS, Wim-
dc.date.accessioned2009-10-27T09:49:50Z-
dc.date.available2009-10-27T09:49:50Z-
dc.date.issued2009-
dc.identifier.citationKralovic, R; Niwinski, D (Ed.) MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2009. p. 369-381.-
dc.identifier.isbn978-3-642-03815-0-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/1942/9900-
dc.description.abstractWe 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.-
dc.format.extent461670 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoen-
dc.publisherSPRINGER-VERLAG BERLIN-
dc.relation.ispartofseriesLecture Notes in Computer Science-
dc.titleRegular Expressions with Counting: Weak versus Strong Determinism-
dc.typeProceedings Paper-
local.bibliographicCitation.authorsKralovic, R; Niwinski, D-
local.bibliographicCitation.conferencename34th International Symposium on Mathematical Foundations of Computer Science-
local.bibliographicCitation.conferenceplaceNovy Smokovec, SLOVAKIA? AUG 24-28, 2009-
dc.identifier.epage381-
dc.identifier.spage369-
dc.identifier.volume5734-
local.format.pages13-
local.bibliographicCitation.jcatC1-
dc.description.notes[Gelade, Wouter; Gyssens, Marc] Hasselt Univ, Hasselt, Belgium.-
local.type.refereedRefereed-
local.type.specifiedProceedings Paper-
local.relation.ispartofseriesnr5734-
dc.bibliographicCitation.oldjcatC1-
dc.identifier.isi000269937800029-
local.bibliographicCitation.btitleMATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2009-
item.fulltextWith Fulltext-
item.validationecoom 2010-
item.accessRightsOpen Access-
item.fullcitationGELADE, Wouter; GYSSENS, Marc & MARTENS, Wim (2009) Regular Expressions with Counting: Weak versus Strong Determinism. In: Kralovic, R; Niwinski, D (Ed.) MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2009. p. 369-381..-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
mfcs09.pdf450.85 kBAdobe PDFView/Open
Show simple item record

WEB OF SCIENCETM
Citations

4
checked on Jun 23, 2022

Page view(s)

42
checked on May 20, 2022

Download(s)

84
checked on May 20, 2022

Google ScholarTM

Check

Altmetric


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