Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13185
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | GELADE, Wouter | - |
dc.contributor.author | GYSSENS, Marc | - |
dc.contributor.author | MARTENS, Wim | - |
dc.date.accessioned | 2012-02-23T15:43:56Z | - |
dc.date.available | 2012-02-23T15:43:56Z | - |
dc.date.issued | 2012 | - |
dc.identifier.citation | SIAM JOURNAL ON COMPUTING, 41(1), p. 160-190 | - |
dc.identifier.issn | 0097-5397 | - |
dc.identifier.uri | http://hdl.handle.net/1942/13185 | - |
dc.description.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. | - |
dc.description.sponsorship | Fund for Scientific Research – Flanders; North-Rhine Westphalian Academy of Sciences, Humanities and Arts; Stiftung Mercator Essen. | - |
dc.language.iso | en | - |
dc.rights | © 2012 Society for Industrial and Applied Mathematics | - |
dc.title | Regular Expressions with Counting: Weak versus Strong Determinism | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 190 | - |
dc.identifier.issue | 1 | - |
dc.identifier.spage | 160 | - |
dc.identifier.volume | 41 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.relation.references | 1. A. Br¨uggemann-Klein. Regular expressions into finite automata. Theor. Comput. Sci., 120(2):197–213, 1993. 2. A. Br¨uggemann-Klein and D. Wood. One-unambiguous regular languages. Information and Computation, 142(2):182–206, 1998. 3. D. Colazzo, G. Ghelli, and C. Sartiani. Efficient asymmetric inclusion between regular expression types. In ICDT, pages 174–182, 2009. 4. S. Dal-Zilio and D. Lugiez. XML schema, tree logic and sheaves automata. In RTA, pages 246–263, 2003. 5. J. Esparza. Decidability and complexity of Petri net problems – an introduction. In Petri Nets, pages 374–428, 1996. 6. M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979. 7. W. Gelade, W. Martens, and F. Neven. Optimizing schema languages for XML: Numerical constraints and interleaving. In ICDT, pages 269–283, 2007. 8. W. Gelade. Succinctness of regular expressions with interleaving, intersection and counting. In MFCS, pages 363–374, 2008. 9. A. Hume. A tale of two greps. Softw., Pract. and Exp., 18(11):1063–1072, 1988. 10. P. Kilpel¨ainen. Inclusion of unambiguous #res is NP-hard, May 2004. Unpublished. 11. P. Kilpel¨ainen and R. Tuhkanen. Regular expressions with numerical occurrence indicators — preliminary results. In SPLST 2003, pages 163–173, 2003. 12. P. Kilpel¨ainen and R. Tuhkanen. Towards efficient implementation of XML schema content models. In DOCENG 2004, pages 239–241. ACM, 2004. 13. P. Kilpel¨ainen and R. Tuhkanen. One-unambiguity of regular expressions with numeric occurrence indicators. Inform. Comput., 205(6):890–916, 2007. 14. C. Koch and S. Scherzinger. Attribute grammars for scalable query processing on XML streams. VLDB Journal, 16(3):317–342, 2007. 15. W. Martens, F. Neven, and T. Schwentick. Complexity of decision problems for simple regular expressions. In MFCS, pages 889–900, 2004. 16. A.R. Meyer and L.J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In FOCS, p. 125–129, 1972. 17. D.W. Mount. Bioinformatics: Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press, September 2004. 18. H. Seidl, T. Schwentick, A. Muscholl, and P. Habermehl. Counting in Trees for Free. In ICALP, pages 1136–1149, 2004. 19. G. Pighizzini and J. Shallit. Unary language operations, state complexity and Jacobsthal’s function. Int. J. Found. Comp. Sc., 13(1):145–159, 2002. 20. C.M. Sperberg-McQueen. Notes on finite state automata with counters. http://www.w3.org/XML/2004/05/msm-cfa.html, 2004. 21. C.M. Sperberg-McQueen and H. Thompson. XML Schema. http://www.w3.org/XML/Schema, 2005. 22. M.Y. Vardi. From monadic logic to PSL. In Pillars of Computer Science, pages 656–681, 2008. 23. L. Wall, T. Christiansen, and J. Orwant. Programming Perl. O’Reilly, 2000. | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1137/100814196 | - |
dc.identifier.isi | 000300892300008 | - |
item.fullcitation | GELADE, Wouter; GYSSENS, Marc & MARTENS, Wim (2012) Regular Expressions with Counting: Weak versus Strong Determinism. In: SIAM JOURNAL ON COMPUTING, 41(1), p. 160-190. | - |
item.contributor | GELADE, Wouter | - |
item.contributor | GYSSENS, Marc | - |
item.contributor | MARTENS, Wim | - |
item.validation | ecoom 2013 | - |
item.accessRights | Open Access | - |
item.fulltext | With Fulltext | - |
crisitem.journal.issn | 0097-5397 | - |
crisitem.journal.eissn | 1095-7111 | - |
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 Sep 20, 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.