טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentDubov Yulia
SubjectInfinite Alphabet Pushdown Automata: Various Approaches and
Comparison of Their Consequences
DepartmentDepartment of Computer Science
Supervisor Professor Michael Kaminski
Full Thesis textFull thesis text - English Version


Abstract

The research of automata over infinite alphabets started as purely theoretical, but soon found its applications. Naturally, every time a string of words is considered - be it messages passing through the network, URLs clicked by Internet surfer, or XML elements content - words are treated as atomic symbols, i.e. elements of an alphabet, and in the absence of a bound on the length of the words, the alphabet becomes infinite.

One approach to dealing with infinite alphabets is a class of models known as register automata. The common idea behind the various models of such automata is as follows: they are analogous to the finite automata in that they have a finite set of states, while the ability to deal with infinite alphabets is achieved by a finite number of registers, each capable of storing any letter from the infinite input alphabet. They can read symbols from the input, compare them to the registers, and proceed according to the results. They also must have some mechanism - reassignment - for altering the contents of the registers.

This general outline presents a range for variations, found in different works, and yielding models of either the same or different power. Another direction of development of this theory is adding a pushdown store to the model, defining a grammar, and developing the infinite alphabet counterpart of context-free languages.

In our work we define infinite-alphabet pushdown automata with deterministic reassignment (DR-IPDA) - a model very similar to the existing infinite-alphabet push-down automata (IPDA), but with deterministic reassignment. We show that this variation yields a weaker automaton by presenting a separating example. We also show that lookahead finite memory automata (LFMA) can be simulated by DR-IPDA.

In another part of the work, we define unification-based push-down automata with non-deterministic reassignment (NR-UBPDA) by adding a push-down store and non-deterministic reassignment to an existing model, finite-state unification-based automata (FSUBA). We also define a variation of context-free grammar over infinite alphabets, and show its equivalence to NR-UBPDA. Finally, we present DR-UBPDA - unification based pushdown automata with deterministic reassignment, and show its equivalence to NR-UBPDA.