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.
http://hal.univ-reunion.fr/hal-01915093
Contributor : Réunion Univ
<>
Submitted on : Wednesday, November 7, 2018 - 12:29:35 PM
Last modification on : Thursday, March 28, 2019 - 11:24:11 AM
Long-term archiving on : Friday, February 8, 2019 - 1:58:52 PM
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⟩
