A Note on Two-pebble Automata Over Infinite Alphabets

• Autorzy: Kaminski M. , Tan T.
• Języki publikacji: EN

Abstrakty

EN

It is shown that the emptiness problemfor two-pebble automata languages is undecidable and that two-pebble automata are weaker than three-pebble automata.

Słowa kluczowe

EN

pebble automata; infinite alphabets; undecidability; Hilbert's tenth problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 98, nr 4
• Strony: 379--390
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Kaminski M.

autor

Tan T.

• Department of Computer Science Technion - Israel Institute of Technology Haifa 32000, Israel,

Bibliografia

• [1] David, C.: Mots et donn´ees infinies, Master Thesis, Universit´e Paris 7, LIAFA, 2004.
• [2] Davis, M.: Hilbert's tenth problem is unsolvable, The American Mathematical Monthly, 80, 1973, 233-269.
• [3] Hopcroft, J., Ullman, J.: Introduction to automata theory, languages, and computation, Addison-Wesley, Reading, MA, 1979.
• [4] Kaminski, M., Francez, N.: Finite-memory automata, Theoretical Computer Science, 134, 1994, 329-363.
• [5] Matijaseviˇc, J.: Enumerable sets are Diophantine, Soviet Mathematics. Doklady, 11, 1970, 354-358.
• [6] Matiyasevich, Y.: Hilbert's Tenth Problem, MIT Press, Cambridge, MA, 1993.
• [7] Neven, F.: Automata, logic, and XML, Computer Science Logic: 16th International Workshop, CSL 2002
• [8] Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets, ACM Transactions on Computational Logic, 5, 2004, 403-435.
• [9] Post, E.: A variant of a recursively unsolvable problem, Bulletin of the American Mathematical Society, 52, 1946, 264-268.
• [10] Tan, T.: Graph Reachability and Pebble Automata over Infinite Alphabets, Proceedings of the 24th IEEE Symposium on Logic in Computer Science (LICS 2009), IEEE Computer Society, Los Alamitos, CA, 2009.
• [11] Tan, T.: On pebble automata for data languages with decidable emptiness problem, Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009 (R. Královic, D. Niwinski, Eds.), Lecture Notes in Computer Science, 5734, pp. 712-723, Springer, Berlin, 2009.