Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
265--290
Opis fizyczny
bibliogr. 17 poz.
Twórcy
autor
- IREMIA, Universite de la Reunion, BP 7151, 97715 Saint Denis Messageries Cedex 9, Reunion, epayet@univ-reunion.fr
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS1-0008-0045