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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brüggemann-Klein, A.: Regular expressions into finite automata. Theor. Comput. Sci. 120(2), 197–213 (1993)
Brüggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Information and Computation 142(2), 182–206 (1998)
Colazzo, D., Ghelli, G., Sartiani, C.: Efficient asymmetric inclusion between regular expression types. In: ICDT, pp. 174–182 (2009)
Dal-Zilio, S., Lugiez, D.: XML schema, tree logic and sheaves automata. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol. 2706, pp. 246–263. Springer, Heidelberg (2003)
Esparza, J.: Decidability and complexity of Petri net problems – an introduction. In: Petri Nets, pp. 374–428 (1996)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Gelade, W., Martens, W., Neven, F.: Optimizing schema languages for XML: Numerical constraints and interleaving. In: Schwentick, T., Suciu, D. (eds.) ICDT 2007. LNCS, vol. 4353, pp. 269–283. Springer, Heidelberg (2007)
Gelade, W.: Succinctness of regular expressions with interleaving, intersection and counting. In: Ochmański, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 363–374. Springer, Heidelberg (2008)
Hume, A.: A tale of two greps. Softw. Pract. and Exp. 18(11), 1063–1072 (1988)
Kilpeläinen, P.: Inclusion of unambiguous #res is NP-hard (May 2004) (unpublished)
Kilpeläinen, P., Tuhkanen, R.: Regular expressions with numerical occurrence indicators — preliminary results. In: SPLST 2003, pp. 163–173 (2003)
Kilpeläinen, P., Tuhkanen, R.: Towards efficient implementation of XML schema content models. In: DOCENG 2004, pp. 239–241. ACM, New York (2004)
Kilpeläinen, P., Tuhkanen, R.: One-unambiguity of regular expressions with numeric occurrence indicators. Inform. Comput. 205(6), 890–916 (2007)
Koch, C., Scherzinger, S.: Attribute grammars for scalable query processing on XML streams. VLDB Journal 16(3), 317–342 (2007)
Martens, W., Neven, F., Schwentick, T.: Complexity of decision problems for simple regular expressions. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 889–900. Springer, Heidelberg (2004)
Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: FOCS, pp. 125–129 (1972)
Mount, D.W.: Bioinformatics: Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press (September 2004)
Seidl, H., Schwentick, T., Muscholl, A., Habermehl, P.: Counting in trees for free. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1136–1149. Springer, Heidelberg (2004)
Pighizzini, G., Shallit, J.: Unary language operations, state complexity and Jacobsthal’s function. Int. J. Found. Comp. Sc. 13(1), 145–159 (2002)
Sperberg-McQueen, C.M.: Notes on finite state automata with counters (2004), http://www.w3.org/XML/2004/05/msm-cfa.html
Sperberg-McQueen, C.M., Thompson, H.: XML Schema (2005), http://www.w3.org/XML/Schema
Vardi, M.Y.: From monadic logic to PSL. Pillars of Computer Science, 656–681 (2008)
Wall, L., Christiansen, T., Orwant, J.: Programming Perl. O’Reilly, Sebastopol (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gelade, W., Gyssens, M., Martens, W. (2009). Regular Expressions with Counting: Weak versus Strong Determinism. In: Královič, R., Niwiński, D. (eds) Mathematical Foundations of Computer Science 2009. MFCS 2009. Lecture Notes in Computer Science, vol 5734. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03816-7_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-03816-7_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03815-0
Online ISBN: 978-3-642-03816-7
eBook Packages: Computer ScienceComputer Science (R0)