Codes engendrant certains systèmes sofiques. (Codes generating certain sofic systems)

DOI10.1016/0304-3975(89)90163-1MaRDI QIDQ1824713zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 1989

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(89)90163-1

zbMATH Keywords

finite circular codesreturn codessofic systemsubshifts of finite type

Mathematics Subject Classification ID

Measure-preserving transformations (28D05) Linear codes (general theory) (94B05)

Review text

The author defines the terms ``local code and ``local code with finite splitting to the left and right and shows that a sofic system is of finite type (respectively almost finite type) if and only if all first return codes are local (respectively local with unique splitting to the right and left). \textit{A. Restivo} [Inf. Control 25, 93-101 (1974; Zbl 0279.68054)] proved that finite circular codes generate subshifts of finite type. The author proves the following: (i) local codes are circular, (ii) finite local codes are identical to finite circular codes, (iii) finite codes with unique splitting are identical to finite codes with finite deciphering delay to the same side. The paper finishes by showing that finite codes with unique splitting to the left and right generate almost finite type subshifts. This does not happen when the finiteness condition is dropped.

Recommendations

• Codes, unambiguous automata and sofic systems.
• Complete Codes in a Sofic Shift
• Codes and sofic constraints
• Completing codes in a sofic shift
• scientific article; zbMATH DE number 4131691

Cites work

• A Note on Minimal Covers for Sofic Systems
• Codes and local constraints
• Ergodic theory on compact spaces
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1988973 (Why is no real title available?)
• On a question of McNaughton and Papert
• On sofic systems. I
• Subshifts of finite type and sofic systems
• Systèmes codés. (Coded systems)

Cited in

(8)

• A note on renewal systems
• Finitely generated sofic systems
• Reducibility of covers of AFT shifts
• Codes, unambiguous automata and sofic systems.
• A hierarchy of shift equivalent sofic shifts
• scientific article; zbMATH DE number 4131691 (Why is no real title available?)
• Finitary codes for biinfinite words
• Complete Codes in a Sofic Shift

This page was built for publication: Codes engendrant certains systèmes sofiques. (Codes generating certain sofic systems)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1824713)