Skip to main content
SpringerLink
Log in

Automata and Logics for Words and Trees over an Infinite Alphabet

  • Conference paper
Computer Science Logic (CSL 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4207))

Included in the following conference series:

Abstract

In a data word or a data tree each position carries a label from a finite alphabet and a data value from some infinite domain. These models have been considered in the realm of semistructured data, timed automata and extended temporal logics.

This paper survey several know results on automata and logics manipulating data words and data trees, the focus being on their relative expressive power and decidability.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Alon, N., Milo, T., Neven, F., Suciu, D., Vianu, V.: XML with Data Values: Typechecking Revisited. Journal of Computer and System Sciences 66(4), 688–727 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  2. Arenas, M., Fan, W., Libkin, L.: Consistency of XML specifications. In: Bertossi, L., Hunter, A., Schaub, T. (eds.) Inconsistency Tolerance. LNCS, vol. 3300, pp. 15–41. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  3. Autebert, J.-M., Beauquier, J., Boasson, L.: Langages des alphabets infinis. Discrete Applied Mathematics 2, 1–20 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  4. Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. In: Proc. ACM Symp. on Principles of Database Systems, pp. 25–36 (2005)

    Google Scholar 

  5. Björklund, H., Schwentick, T.: Personnal communication

    Google Scholar 

  6. Bojańczyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two- Variable Logic on Data Trees and XML Reasoning. In: Proc. ACM Symp. on Principles of Database Systems (2006)

    Google Scholar 

  7. Bojańczyk, M., Muscholl, A., Schwentick, T., Segoufin, L., David, C.: Two- Variable Logic on Words with Data. In: Proc. IEEE Conf. on Logic in Computer Science (2006)

    Google Scholar 

  8. Bouajjani, A., Habermehl, P., Mayr, R.: Automatic Verification of Recursive Procedures with one Integer Parameter. Theoretical Computer Science 295 (2003)

    Google Scholar 

  9. Bouyer, P., Petit, A., Thérien, D.: An algebraic approach to data languages and timed languages. Inf. Comput. 182(2), 137–162 (2003)

    Article  MATH  Google Scholar 

  10. Buneman, P., Davidson, S.B., Fan, W., Hara, C.S., Tan, W.C.: Reasoning about keys for XML. Inf. Syst. 28(8), 1037–1063 (2003)

    Article  Google Scholar 

  11. Cheng, E., Kaminski, M.: Context-Free Languages over Infinite Alphabets. Acta Inf. 35(3), 245–267 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  12. David, C.: Mots et données infinis. Master’s thesis, Université Paris 7, LIAFA (2004)

    Google Scholar 

  13. de Groote, P., Guillaume, B., Salvati, S.: Vector Addition Tree Automata. In: Proc. IEEE Conf. on Logic in Computer Science, pp. 64–73 (2004)

    Google Scholar 

  14. Demri, S., Lazić, R.: LTL with the Freeze Quantifer and Register Automata. In: Proc. IEEE Conf. on Logic in Computer Science (2006)

    Google Scholar 

  15. Demri, S., Lazić, R., Nowak, D.: On the freeze quantifier in Constraint LTL. In: TIMES (2005)

    Google Scholar 

  16. Etessami, K., Vardi, M., Wilke, T.: First-Order Logic with Two Variables and Unary Temporal Logic. Inf. Comput. 179(2), 279–295 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  17. Francez, N., Kaminski, M.: An algebraic characterization of deterministic regular languages over infinite alphabets. Theoretical Computer Science 306(1-3), 155–175 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  18. Geerts, F., Fan, W.: Satisfiability of XPath Queries with Sibling Axes. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 122–137. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  19. Idt, J.: Automates a pile sur des alphabets infinis. In: Fontet, M., Mehlhorn, K. (eds.) STACS 1984. LNCS, vol. 166. Springer, Heidelberg (1984)

    Google Scholar 

  20. Kaminski, M., Francez, N.: Finite memory automata. Theoretical Computer Science 134(2), 329–363 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  21. Kaminski, M., Tan, T.: Regular Expressions for Languages over Infinite Alphabets. Fundam. Inform. 69(3), 301–318 (2006)

    MATH  MathSciNet  Google Scholar 

  22. Kaminski, M., Tan, T.: Tree Automata over Infinite Alphabets. In: H. Ibarra, O., Yen, H.-C. (eds.) CIAA 2006. LNCS, vol. 4094. Springer, Heidelberg (2006)

    Google Scholar 

  23. Kosaraju, S.: Decidability of reachability in vector addition systems. In: Proc. ACM SIGACT Symp. on the Theory of Computing, pp. 267–281 (1984)

    Google Scholar 

  24. Lipton, R.: The reachability problem requires exponential space. Technical report, Dep. of Comp. Sci., Research report 62, Yale University (1976)

    Google Scholar 

  25. Marx, M.: First order paths in ordered trees. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 114–128. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  26. Mayr, E.: An algorithm for the general Petri net reachability problem. SIAM J. of Comp. 13, 441–459 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  27. Neven, F., Schwentick, T.: XPath Containment in the Presence of Disjunction, DTDs, and Variables. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 312–326. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  28. Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Logic 15(3), 403–435 (2004)

    Article  MathSciNet  Google Scholar 

  29. Otto, F.: Classes of regular and context-free languages over countably infinite alphabet. Discrete and Apllied Mathematics 12, 41–56 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  30. Sakamoto, H., Ikeda, D.: Intractability of decision problems for finite-memory automata. Theoretical Computer Science 231, 297–308 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  31. Shemesh, Y., Francez, N.: Finite-State Unification Automata and Relational Languages. Inf. Comput. 114(2), 192–213 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  32. Tal, A.: Decidability of inclusion for unification based automata. Master’s thesis, Department of Computer Science, Technion - Israel Institute of Technology (1999)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. INRIA and Université Paris 11,  

    Luc Segoufin

Authors
  1. Luc Segoufin
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Research Group on Mathematical Linguistics, Rovira i Virgili University, Tarragona, Spain

    Zoltán Ésik

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Segoufin, L. (2006). Automata and Logics for Words and Trees over an Infinite Alphabet. In: Ésik, Z. (eds) Computer Science Logic. CSL 2006. Lecture Notes in Computer Science, vol 4207. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11874683_3

Download citation

  • DOI: https://doi.org/10.1007/11874683_3

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-45458-8

  • Online ISBN: 978-3-540-45459-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation