Skip to Main content Skip to Navigation
Conference papers

On Rational Trees

Arnaud Carayol 1 Christophe Morvan 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 : Rational graphs are a family of graphs defined using labelled rational transducers. Unlike automatic graphs (defined using synchronized transducers) the first order theory of these graphs is undecidable, there is even a rational graph with an undecidable first order theory. In this paper we consider the family of rational trees, that is rational graphs which are trees. We prove that first order theory is decidable for this family. We also present counter examples showing that this result cannot be significantly extended both in terms of logic and of structure.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Arnaud Carayol Connect in order to contact the contributor
Submitted on : Monday, October 3, 2011 - 2:11:24 PM
Last modification on : Friday, February 4, 2022 - 3:18:36 AM
Long-term archiving on: : Wednesday, January 4, 2012 - 2:26:41 AM


Files produced by the author(s)


  • HAL Id : hal-00620171, version 1


Arnaud Carayol, Christophe Morvan. On Rational Trees. 20th International Conference on Computer Science Logic (CSL'06), Sep 2006, Szeged, Hungary. pp.225-239. ⟨hal-00620171⟩



Record views


Files downloads