• Calendar

December 4, Tuesday
12:00 – 13:00

Pebble automata (PA) over infinite alphabets are an extension of the classical PA. They were introduced by Neven, Schwentick, and V. Vianu about ten years ago and recently found applications in XML. The notion of PA over infinite alphabets is very robust. In addition to equivalence of various models of PA, the set of languages they accept is closed under all Boolean operations. However, the emptiness problem for these languages is undecidable for three or more pebbles. Reducing Hilbert's tenth problem to the emptiness problem for 2-PA languages, we prove that the latter is also undecidable. In addition, we present an example of a 3-PA language that is not accepted by 2-PA, i,e., 2-PA automata are weaker than 3-PA. Finally, we show that 2-PA can accept a non-semi-linear language. The talk does not presume any prior knowledge of models of computation over infinite alphabets. Joint work with Tony Tan.