Synchronized Product of Linear Bounded Machines - Archive ouverte HAL Access content directly
Conference Papers Year : 1999

Synchronized Product of Linear Bounded Machines

(1) , (1)
1

Abstract

This paper introduces a class of graphs associated to linear bounded machines. It is shown that this class is closed, up to observational equivalence, under synchronized product. The first-order theory of these graphs is investegated and shown to be undecidable. The latter result extends to any logic in which the existence of sinks may be stated.
Fichier principal
Vignette du fichier
Chapter_Synchronized_Product_Of_Linear_Bounded_machines.pdf (192.16 Ko) Télécharger le fichier
Origin : Explicit agreement for this submission
Loading...

Dates and versions

hal-01915093 , version 1 (07-11-2018)

Identifiers

  • HAL Id : hal-01915093 , version 1

Cite

Teodor Knapik, Etienne Payet. Synchronized Product of Linear Bounded Machines. 12th International Symposium on Fundamentals of Computation Theory (FCT'99), Alexandru Ioan Cuza University, Aug 1999, Iasi, Romania. pp.362-373. ⟨hal-01915093⟩
30 View
137 Download

Share

Gmail Facebook Twitter LinkedIn More