2008/10/31 by Uijin Jung · 19 citations
Computer Science · Mathematics · #Cellular Automata and Applications #Code (set theory) #Coding theory and cryptography #Entropy (arrow of time) #Irreducible representation #Subshift of finite type #Type (biology) #math.DS #msc:37B10 #msc:37B40 #semigroups and automata theory
paper · pdf · doi:10.1090/s0002-9947-2010-05035-4
published in Transactions of the American Mathematical Society 363(3), 1399-1417 (American Mathematical Society) · 20 pages, 3 figures. v2: minor revision. typos corrected. Final version to appear in Transactions AMS
arxiv created 2009/02/27 · openalex publication_date 2010/10/20 · arxiv updated 2013/11/26 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
Given an irreducible sofic shift <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , we show that an irreducible shift of finite type <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper Y"> <mml:semantics> <mml:mi>Y</mml:mi> <mml:annotation encoding="application/x-tex">Y</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of lower entropy is a factor of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> if and only if it is a factor of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> by an open bi-continuing code. If these equivalent conditions hold and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper Y"> <mml:semantics> <mml:mi>Y</mml:mi> <mml:annotation encoding="application/x-tex">Y</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is mixing, then any code from a proper subshift of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper Y"> <mml:semantics> <mml:mi>Y</mml:mi> <mml:annotation encoding="application/x-tex">Y</mml:annotation> </mml:semantics> </mml:math> </inline-formula> can be extended to an open bi-continuing code on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . These results are still valid when <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is assumed to be only an almost specified shift, i.e., a subshift satisfying an irreducible version of the specification property.