Abstract
In data words, each position carries not only a letter form a finite alphabet, as the usual words do, but also a data value coming from an infinite domain. There has been a renewed interest in them due to applications in querying and reasoning about data models with complex structural properties, notably XML, and more recently, graph databases. Logical formalisms designed for querying such data often require concise and easily understandable presentations of regular languages over data words.
Our goal, therefore, is to define and study regular expressions for data words. As the automaton model, we take register automata, which are a natural analog of NFAs for data words. We first equip standard regular expressions with limited memory, and show that they capture the class of data words defined by register automata. The complexity of the main decision problems for these expressions (nonemptiness, membership) also turns out to be the same as for register automata. We then look at a subclass of these regular expressions that can define many properties of interest in applications of data words, and show that the main decision problems can be solved efficiently for it.
This is a preview of subscription content, log in via an institution to check access.
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
Angles, R., Gutiérrez, C.: Survey of graph database models. ACM Comput. Surv. 40(1) (2008)
Barceló, P., Hurtado, C., Libkin, L., Wood, P.: Expressive languages for path queries over graph-structured data. In: PODS 2010, pp. 3–14 (2010)
Benedikt, M., Ley, C., Puppis, G.: Automata vs. Logics on Data Words. In: Dawar, A., Veith, H. (eds.) CSL 2010. LNCS, vol. 6247, pp. 110–124. Springer, Heidelberg (2010)
Bojanczyk, M., Parys, P.: XPath evaluation in linear time. In: PODS 2008, pp. 241–250 (2008)
Bojanczyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on words with data. ACM TOCL 12(4) (2011)
Bojanczyk, M., Lasota, S.: An extension of data automata that captures XPath. In: LICS 2010, pp. 243–252 (2010)
Calvanese, D., de Giacomo, G., Lenzerini, M., Vardi, M.Y.: Rewriting of regular expressions and regular path queries. JCSS 64(3), 443–465 (2002)
Colcombet, T., Ley, C., Puppis, G.: On the Use of Guards for Logics with Data. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 243–255. Springer, Heidelberg (2011)
Demri, S., Lazic, R.: LTL with the freeze quantifier and register automata. ACM TOCL 10(3) (2009)
Figueira, D.: Satisfiability of downward XPath with data equality tests. In: PODS 2009, pp. 197–206 (2009)
Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. IPL 59, 75–77 (1996)
Grumberg, O., Kupferman, O., Sheinvald, S.: Variable Automata over Infinite Alphabets. In: Dediu, A.-H., Fernau, H., Martín-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 561–572. Springer, Heidelberg (2010)
Kaminski, M., Francez, N.: Finite memory automata. Theoretical Computer Science 134(2), 329–363 (1994)
Kaminski, M., Tan, T.: Regular expressions for languages over infinite alphabets. Fundam. Inform. 69(3), 301–318 (2006)
Libkin, L.: Logics for unranked trees: an overview. Logical Methods in Computer Science 2(3) (2006)
Libkin, L., Vrgoč, D.: Regular path queries on graphs with data. In: ICDT 2012 (to appear, 2012)
Marx, M.: Conditional XPath. ACM TODS 30, 929–959 (2005)
Mendelzon, A.O., Wood, P.T.: Finding regular simple paths in graph databases. SIAM J. Comput. 24(6), 1235–1258 (1995)
Neven, F.: Automata theory for XML researchers. SIGMOD Record 31(3), 39–46 (2002)
Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM TOCL 5(3), 403–435 (2004)
Sakamoto, H., Ikeda, D.: Intractability of decision problems for finite-memory automata. Theor. Comput. Sci. 231(2), 297–308 (2000)
Schwentick, T.: Automata for XML – A survey. JCSS 73(3), 289–315 (2007)
Segoufin, L.: Automata and Logics for Words and Trees over an Infinite Alphabet. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 41–57. Springer, Heidelberg (2006)
Sipser, M.: Introduction to the Theory of Computation. PWS Publishing (1997)
Tan, T.: Graph reachability and pebble automata over infinite alphabets. In: LICS 2009, pp. 157–166 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Libkin, L., Vrgoč, D. (2012). Regular Expressions for Data Words. In: Bjørner, N., Voronkov, A. (eds) Logic for Programming, Artificial Intelligence, and Reasoning. LPAR 2012. Lecture Notes in Computer Science, vol 7180. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28717-6_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-28717-6_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28716-9
Online ISBN: 978-3-642-28717-6
eBook Packages: Computer ScienceComputer Science (R0)