My PhD dissertation

Information on my PhD. thesis. My advisor was Christian Choffrut and I undertook this at LIAFA, Université Paris VII. The dissertation is written in French, but papers and this abstract are in english.

French version

WORM (write once, read many) tracks can be used to extend the input tapes of various two-way automata. Extending two-way finite deterministic automata (resp. non-deterministic automata, deterministic automata with a pebble) gives WORM-2DFAs (resp. WORM-2NFAs, P-WORM-2DFAs) whose languages are regular, whereas extending two-way finite alternating (WORM-2AFAs) or non-deterministic pebble (P-WORM-2NFAs) automata gives models which can recognize non-regular languages. The collage of a word or picture language is a new language whose elements are made by stacking at various positions elements of that language. This operation can be easily performed on a WORM track. The collage of a regular word language is also regular, albeit its automaticity can rise exponentially. However the collage of a recognizable picture language is not necessarily recognizable, even on a language made of two elements over three colors. WORM tracks have originally been introduced to extend two-way deterministic pushdown automata (2DPDAs). These automata are closely related to the languages recognizable in polynomial time. We do not know if WORM-2DPDAs recognize more languages than 2DPDAs. In order to ease the exploration of their capabilities and in the hope of finding a separating language, we have designed a structured language for 2DPDAs and WORM-2DPDAs, called Diamond.

The following are in french:

English material:

2005-12-10