HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Thue specifications, infinite graphs and synchronized product

Abstract : This paper presents some formal verification-oriented results about the class of graphs associated with Thue specifications. It is shown that this class is closed, up to isomorphism, under synchronized product. It is also established that every rational graph with no edge labeled by the empty word is isomorphic to the graph of a Thue specification. A consequence of this result is that the first-order theory of the graphs of Thue specifications is undecidable. Connections between graphs of Thue specifications and those of Turing machines are finally investigated. The main result is that the graph of each Thue specification is observationally equivalent to that of a Turing machine but the reverse does not hold.
Document type :
Journal articles
Complete list of metadata

Contributor : Réunion Univ Connect in order to contact the contributor
Submitted on : Wednesday, November 7, 2018 - 1:14:22 PM
Last modification on : Tuesday, October 19, 2021 - 5:56:07 PM
Long-term archiving on: : Friday, February 8, 2019 - 2:27:46 PM


  • HAL Id : hal-01915145, version 1



Etienne Payet. Thue specifications, infinite graphs and synchronized product. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2000, 44 (3), pp.265-290. ⟨hal-01915145⟩



Record views


Files downloads