Skip to Main content Skip to Navigation
Conference papers

Traces of Term-Automatic Graphs

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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00681214
Contributor : Antoine Meyer <>
Submitted on : Wednesday, March 21, 2012 - 12:28:38 AM
Last modification on : Thursday, November 19, 2020 - 11:48:02 AM
Long-term archiving on: : Monday, November 26, 2012 - 11:45:16 AM

File

mfcs-paper095.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Antoine Meyer. Traces of Term-Automatic Graphs. Mathematical Foundations of Computer Science (MFCS), Aug 2007, Cesky Krumlov, Poland. p. 489-500, ⟨10.1007/978-3-540-74456-6_44⟩. ⟨hal-00681214⟩

Share

Metrics

Record views

332

Files downloads

579