RAIRO - Theoretical Informatics and Applications

Table of Contents - July 2008 - Volume 42, Issue 03 (JM'06)  

Research Article

Traces of term-automatic graphs

Meyer, Antoine

LIAFA, Université Paris Diderot – Paris 7 & CNRS, France; ameyer@liafa.jussieu.fr

Abstract

In formal language theory, many families of languages are defined using either grammars or finite acceptors. For instance, context-sensitive languages are the languages generated by growing grammars, or equivalently those accepted by Turing machines whose work tape's size is proportional to that of their input. A few years ago, a new characterisation of context-sensitive languages as the sets of traces, or path labels, of rational graphs (infinite graphs defined by sets of finite-state transducers) was established. We investigate a similar characterisation in the more general framework of graphs defined by term transducers. In particular, we show that the languages of term-automatic graphs between regular sets of vertices coincide with the languages accepted by alternating linearly bounded Turing machines.
As a technical tool, we also introduce an arborescent variant of tiling systems, which provides yet another characterisation of these languages.

(Online publication June 3 2008)

Key Words:

  • Languages;
  • infinite automata;
  • terms;
  • tiling systems;
  • complexity.

Mathematics Subject Classification:

  • 68Q45;
  • 68Q05