Skip to Main content Skip to Navigation
Conference papers

Linearly Bounded Infinite Graphs

Arnaud Carayol 1 Antoine Meyer 2
1 GALION - Graphs, Automata, Logics, Languages and vErificatiON
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, UR1 - Université de Rennes 1, INSA Rennes - Institut National des Sciences Appliquées - Rennes, CNRS - Centre National de la Recherche Scientifique : UMR6074
Abstract : Linearly bounded Turing machines have been mainly studied as acceptors for context-sensitive languages. We define a natural family of canonical infinite automata representing their observable computational behavior, called linearly bounded graphs. These automata naturally accept the same languages as the linearly bounded machines defining them. We present some of their structural properties as well as alternative characterizations in terms of rewriting systems and context-sensitive transductions. Finally, we compare these graphs to rational graphs, which are another family of automata accepting the context-sensitive languages, and prove that in the bounded-degree case, rational graphs are a strict sub-family of linearly bounded graphs.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00149334
Contributor : Antoine Meyer Connect in order to contact the contributor
Submitted on : Tuesday, March 20, 2012 - 9:18:13 PM
Last modification on : Saturday, November 20, 2021 - 3:49:43 AM
Long-term archiving on: : Thursday, June 21, 2012 - 2:20:11 AM

File

carayol-meyer_mfcs05.pdf
Files produced by the author(s)

Identifiers

Citation

Arnaud Carayol, Antoine Meyer. Linearly Bounded Infinite Graphs. MFCS 2005, Sep 2005, Gdansk, Poland. pp.180-191, ⟨10.1007/11549345_17⟩. ⟨hal-00149334⟩

Share

Metrics

Record views

305

Files downloads

90