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.
https://hal.univ-reunion.fr/hal-01915093 Contributor : Réunion UnivConnect in order to contact the contributor Submitted on : Wednesday, November 7, 2018 - 12:29:35 PM Last modification on : Tuesday, October 19, 2021 - 5:56:07 PM 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⟩