On Pebble Automata Over Infinite Alphabets

Speaker:	Tony TAN
		Technion - Israel Institute of Technology

Title:		"On Pebble Automata Over Infinite Alphabets"

Date:		Monday, 20 October 2008

Time:		4:00pm - 5:00pm

Venue:		Lecture Theater F (via lifts 25/26)
		HKUST

Abstract :

Recently there has been an active and broad research programme on logic and
automata for words over infinite alphabets. Some of the motivations are the
need for formal verification and the search for automated reasoning
technique for XML.

In this talk we continue the study of pebble automata for words over
infinite alphabets introduced by F. Neven, T. Schwentick and V. Vianu [1,2].
In essence, pebble automata (PA) are finite state automata with a finite
number of pebbles. The pebbles are placed on the input word in the stack
discipline: first in last out, to mark the input symbols. One pebble can
only mark one symbol and the last pebble placed serves as the header. The
automaton moves from one state to another depending on the equality tests
among symbols marked by the pebbles. As studied in [1,2], PA languages have
desirable closure properties; but undesirable in terms of application: its
emptiness problem in general is undecidable.

In this talk we present the boundary of the subclass of PA languages of
which the emptiness problem is decidable. We also establish the hierarchy of
PA languages based on the number of pebbles. A few of our results settle
problems left open in [1,2]. Moreover, some of the proof techniques may be
of general interest. For example, the proof of the undecidability of the
emptiness problem of the so called strong 2 pebble PA is by reduction from
Hilbert's tenth problem.


Reference :

[1] F. Neven, T. Schwentick, V. Vianu. Towards regular languages over
infinite alphabets.  In the proceedings of 26th International Symposium on
Mathematical Foundations of Computer Science 2001, LNCS 2136.

[2] F. Neven, T. Schwentick, V. Vianu. Finite state machines for strings
over infinite alphabets. ACM Transactions on Computational Logic 5, 3:
403-435, (2004)


***************************
Biography:

Tony Tan is currently pursuing his PhD study and expected to graduate in
2009 in Technion - Israel Institute of Technology. His research interest is
mainly on automata and formal languages, finite model theory (in particular,
0-1 law and satisfiability in finite model) and computational geometry (in
particular, object approximation and deformation). He obtained his B.Comp
and M.Sc. in 2003 and 2005, respectively, both in the School of Computing,
National University of Singapore.