Digitale Bibliotheek
Sluiten Bladeren door artikelen uit een tijdschrift
 
<< vorige   
     Tijdschrift beschrijving
       Alle jaargangen van het bijbehorende tijdschrift
         Alle afleveringen van het bijbehorende jaargang
           Alle artikelen van de bijbehorende aflevering
                                       Details van artikel 4 van 4 gevonden artikelen
 
 
  Thue Specifications, Infinite Graphs and Synchronized Product
 
 
Titel: Thue Specifications, Infinite Graphs and Synchronized Product
Auteur: Étienne Payet
Verschenen in: Fundamenta informaticae
Paginering: Jaargang 44 (2003) nr. 3 pagina's 265-290
Jaar: 2003-07-11
Inhoud: 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.
Uitgever: IOS Press
Bronbestand: Elektronische Wetenschappelijke Tijdschriften
 
 

                             Details van artikel 4 van 4 gevonden artikelen
 
<< vorige   
 
 Koninklijke Bibliotheek - Nationale Bibliotheek van Nederland