Synchronized Product of Linear Bounded Machines

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

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

File

Chapter_Synchronized_Product_O...
Explicit agreement for this submission

Identifiers

  • HAL Id : hal-01915093, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

33

Files downloads

64