 |
HAL UPEC - UPEM Portal |  |
 |
Conference papers
On Rational Trees
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.
Cited literature [15 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00620171
Contributor : Arnaud Carayol <>
Submitted on : Monday, October 3, 2011 - 2:11:24 PM
Last modification on : Friday, July 10, 2020 - 4:21:17 PM
Long-term archiving on: : Wednesday, January 4, 2012 - 2:26:41 AM
Contributor : Arnaud Carayol <>
Submitted on : Monday, October 3, 2011 - 2:11:24 PM
Last modification on : Friday, July 10, 2020 - 4:21:17 PM
Long-term archiving on: : Wednesday, January 4, 2012 - 2:26:41 AM
File
hal.pdf
Files produced by the author(s)