إزاحة فرعية من النوع المحدود

في الرياضيات ، تُعرَّف الإزاحات الجزئية من النوع المحدود بأنها فضاءات إزاحة مُحدَّدة بمجموعة محدودة من الكلمات الممنوعة. تُستخدم هذه الإزاحات لنمذجة الأنظمة الديناميكية ، وهي على وجه الخصوص موضوع دراسة في الديناميكا الرمزية ونظرية الإرجودية . كما أنها تصف مجموعة جميع التسلسلات الممكنة التي تُنفِّذها آلة ذات حالات محدودة . تُعد الإزاحات الجزئية من النوع المحدود أكثر فضاءات الإزاحة دراسةً .

أحد الأمثلة على الإزاحة (أحادية الجانب) من النوع المحدود هو مجموعة جميع المتتاليات، غير المنتهية من طرف واحد فقط، التي يمكن تكوينها من الأحرف${\displaystyle A,B}$، يحب${\displaystyle AAA\cdots ,ABAB\cdots ,\dots }$يُعرف هذا باسم نوبة عمل كاملة ويُشار إليه بـ${\displaystyle \{A,B\}^{\mathbb {N} }}$.

بمنع الكلمة${\displaystyle BB}$، يُعرّف المرء تحولًا من نوع محدود${\displaystyle \Sigma =\{(x_{0},x_{1},x_{2},\ldots )\mid x_{i}x_{i+1}\neq BB\}}$يُطلق عليه اسم التحول الذهبي ، وذلك بسبب عدد الكلمات القانونية ذات الطول${\displaystyle n}$هي أعداد فيبوناتشي . الإزاحات ثنائية الجانب من النوع المحدود متشابهة، ولكنها تتكون من متتاليات لا نهائية من كلا الطرفين.

يمكن تعريف الإزاحة الفرعية بواسطة رسم بياني موجه على الأحرف، مثل الرسم البياني${\displaystyle A\to B\to C\to A}$يتكون من متواليات تكون انتقالاتها بين الأحرف المتتالية هي فقط تلك المسموح بها في الرسم البياني. في هذا المثال، يتكون الإزاحة الفرعية من ثلاث متواليات أحادية الجانب فقط:${\displaystyle ABCABC\cdots ,BCABCA\cdots ,CABCAB\cdots }$وبالمثل، فإن التحول الفرعي ثنائي الجانب الموصوف في هذا الرسم البياني يتكون من ثلاث متواليات ثنائية الجانب فقط.

تُنتج الرسوم البيانية الموجهة الأخرى على نفس الأحرف تحولات فرعية أخرى. على سبيل المثال، إضافة سهم آخر${\displaystyle A\to C}$يؤدي تطبيق هذا الرسم البياني إلى إنشاء إزاحة فرعية، بدلاً من أن تحتوي على ثلاث متواليات، تحتوي على عدد لا نهائي غير قابل للعد من المتواليات. وبإمكان أي إزاحة فرعية من نوع محدود، باستثناء إعادة ترميز محلية للأحرف، أن تُوصف بمثل هذا الرسم البياني الموجه.

يترك${\displaystyle {\mathcal {A}}}$لتكن مجموعة منتهية من${\displaystyle n}$الرموز (الأبجدية). ليكن${\displaystyle X}$يرمز إلى المجموعة${\displaystyle {\mathcal {A}}^{\mathbb {Z} }}$من جميع المتتاليات الثنائية اللانهائية من عناصر${\displaystyle {\mathcal {A}}}$بالإضافة إلى عامل الوردية${\displaystyle T}$نحن نمنح${\displaystyle {\mathcal {A}}}$مع الطوبولوجيا المنفصلة و${\displaystyle X}$مع بنية المنتج . التدفق الرمزي أو الإزاحة الفرعية هو مغلق${\displaystyle T}$مجموعة فرعية ثابتة${\displaystyle Y}$ل${\displaystyle X}$^{[ 1 ]} واللغة المرتبطة بها${\displaystyle {\mathcal {L}}_{Y}}$هي مجموعة الكلمات الجزئية المنتهية لعناصر من${\displaystyle Y}$[ ^{2 ]​}

يترك${\displaystyle F}$لتكن مجموعة محدودة من الكلمات في الأبجدية${\displaystyle {\mathcal {A}}}$والتي تُسمى الكلمات المحظورة . ويُعرَّف الإزاحة الفرعية المرتبطة بها من النوع المحدود بأنها الفضاء

$${\displaystyle \Sigma _{F}=\{(x_{0},x_{1},x_{2},\ldots )\mid \forall i,k\geq 0,x_{i}x_{i+1}\cdots x_{i+k}\notin F\}}$$

من التسلسلات التي تتجنب مجموعة الكلمات المحظورة${\displaystyle F}$.

إذا امتدت المتتالية إلى ما لا نهاية في اتجاه واحد فقط كما هو مذكور أعلاه، فإنها تسمى إزاحة فرعية أحادية الجانب من النوع المحدود، وإذا كانت ثنائية الجانب ، فإنها تسمى إزاحة فرعية ثنائية الجانب من النوع المحدود.

عامل المناوبة${\displaystyle T}$يرسم تسلسلًا في عملية الإزاحة أحادية الجانب أو ثنائية الجانب إلى تسلسل آخر عن طريق إزاحة جميع الرموز إلى اليسار، أي

$${\displaystyle (T(x))_{i}=x_{i+1}.}$$

من الواضح أن هذه الخريطة قابلة للعكس فقط في حالة الإزاحة ثنائية الجانب.

تُعدّ إزاحات الحواف فئة فرعية مفيدة للغاية . لنفترض أن A مصفوفة تجاور من الرتبة n × n عناصرها {0، 1}. باستخدام هذه العناصر، نبني رسمًا بيانيًا موجهًا G = ( V , E ) حيث V مجموعة الرؤوس و E مجموعة الحواف. تحتوي الحافة الموجهة x → y في E إذا وفقط إذا كان A _{(x , y)} = 1. لنفترض أن Y مجموعة جميع المتتاليات اللانهائية المقبولة من الحواف، حيث يُقصد بـ " مقبولة " أن المتتالية تمثل مسارًا في الرسم البياني، ويمكن أن تكون المتتالية لانهائية من جانب واحد أو من جانبين. لنفترض أن T هو عامل الإزاحة إلى اليسار على هذه المتتاليات؛ وهو يؤدي دور عامل التطور الزمني للنظام الديناميكي. تُعرَّف إزاحة الحافة حينها على أنها الزوج ( Y , T ) الناتج بهذه الطريقة.

بصورة رسمية، يمكن تعريف تسلسلات الحواف على النحو التالي:

${\displaystyle \Sigma _{A}^{+}=\left\{(x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {N} \right\}.}$

هذا هو فضاء جميع متواليات الرموز بحيث لا يمكن أن يتبع الرمز p الرمز q إلا إذا كان العنصر ( p , q ) في المصفوفة A يساوي 1. ويتم تعريف فضاء جميع المتواليات الثنائية اللانهائية بشكل مماثل:

${\displaystyle \Sigma _{A}=\left\{(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {Z} \right\}.}$

تُعدّ تحولات الحواف مجموعة فرعية من التحولات الفرعية من النوع المحدود، والتي تتألف مجموعة كلماتها الممنوعة من كلمات ثنائية الأحرف فقط. من جهة أخرى، يمكن إثبات أن كل تحول فرعي من النوع المحدود مترافق طوبولوجيًا مع تحول حافة عبر إعادة ترميز محلي . ^{[ 3 ]}

يُطلق على إزاحة الحافة اسم إزاحة متعدية إذا كانت G متصلة بقوة : أي يوجد تسلسل من الحواف من أي رأس إلى أي رأس آخر. الإزاحات الجزئية من النوع المحدود ذات المدارات الكثيفة هي تحديدًا تلك المترافقة مع إزاحة حافة متعدية.

تُعد حالة الإزاحة الكاملة من الرتبة n حالة خاصة مهمة : فهي تحتوي على رسم بياني بحافة تربط كل رأس بكل رأس آخر؛ أي أن جميع عناصر مصفوفة التجاور تساوي 1. تتوافق الإزاحة الكاملة من الرتبة n مع مخطط برنولي بدون القياس .

بحسب الاصطلاح، يُفهم مصطلح "الإزاحة" على أنه يشير إلى الإزاحة الكاملة من الرتبة n . أما " الإزاحة الجزئية " فهي أي فضاء جزئي من الإزاحة الكاملة يكون ثابتًا تحت تأثير الإزاحة (أي فضاء جزئي ثابت تحت تأثير عامل الإزاحة)، وغير فارغ، ومغلق وفقًا لطوبولوجيا الضرب الموضحة أدناه. يمكن تمييز بعض الإزاحات الجزئية بمصفوفة انتقال، كما ذُكر أعلاه؛ وتُسمى هذه الإزاحات الجزئية حينها "إزاحات جزئية من النوع المحدود". غالبًا ما تُسمى الإزاحات الجزئية من النوع المحدود ببساطة " إزاحات من النوع المحدود" . كما تُسمى أحيانًا " إزاحات ماركوف الطوبولوجية" .

العديد من الأنظمة الديناميكية الفوضوية متماثلة مع التحولات الفرعية من النوع المحدود؛ وتشمل الأمثلة الأنظمة ذات الاتصالات المتماثلة المستعرضة ، والتحولات التفاضلية للمشعبات المغلقة ذات الإنتروبيا المترية الموجبة ، وخرائط ماركوف الخطية القطعية للفترة.

يتمتع التحويل الفرعي ببنية طبيعية، مشتقة من بنية المنتج على${\displaystyle V^{\mathbb {Z} },}$أين​

${\displaystyle V^{\mathbb {Z} }=\prod _{n\in \mathbb {Z} }V=\{x=(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{k}\in V\;\forall k\in \mathbb {Z} \}}$

ويُعطى V الطوبولوجيا المنفصلة . أساس لطوبولوجيا ⁠${\displaystyle V^{\mathbb {Z} },}$والتي تُنتج طوبولوجيا الإزاحة الفرعية، هي عائلة مجموعات الأسطوانات

${\displaystyle C_{t}[a_{0},\ldots ,a_{s}]=\{x\in V^{\mathbb {Z} }:x_{t}=a_{0},\ldots ,x_{t+s}=a_{s}\}}$

مجموعات الأسطوانات هي مجموعات مفتوحة في${\displaystyle V^{\mathbb {Z} }.}$كل مجموعة مفتوحة في${\displaystyle V^{\mathbb {Z} }}$⁠ هو اتحاد قابل للعد لمجموعات الأسطوانات. كل مجموعة مفتوحة في الإزاحة الفرعية هي تقاطع مجموعة مفتوحة من ⁠${\displaystyle V^{\mathbb {Z} }}$مع الإزاحة الفرعية. بالنسبة لهذه الطوبولوجيا، فإن الإزاحة T هي تماثل شكلي ؛ أي أنها بالنسبة لهذه الطوبولوجيا متصلة ولها معكوس متصل.

المساحة​${\displaystyle V^{\mathbb {Z} }}$⁠ متماثلة شكليًا مع مجموعة كانتور .

يمكن تعريف مجموعة متنوعة من المقاييس المختلفة على فضاء الإزاحة. يُمكن تعريف مقياس على فضاء الإزاحة باعتبار نقطتين "متقاربتين" إذا كانتا تشتركان في العديد من الرموز الأولية؛ وهذا هو المقياس p -adic . في الواقع، كل من فضاءات الإزاحة أحادية الجانب وثنائية الجانب هي فضاءات مترية متراصة .

يمكن تزويد إزاحة فرعية من النوع المحدود بأي من عدة مقاييس مختلفة ، مما يؤدي إلى نظام ديناميكي يحافظ على القياس . ومن المواضيع الشائعة للدراسة مقياس ماركوف ، وهو امتداد لسلسلة ماركوف إلى طوبولوجيا الإزاحة.

سلسلة ماركوف هي زوج ( P ، π) يتكون من مصفوفة الانتقال ، ومصفوفة n × n P = ( p_{_ij} ) التي تحقق الشرط التالي: جميع قيم p _{_ij} ≥ 0 و

${\displaystyle \sum _{j=1}^{n}p_{ij}=1}$

لكل i . متجه الاحتمال الثابت π = ( π _i ) له جميع قيم π _i ≥ 0 ،${\textstyle \sum \pi _{i}=1}$وله

${\displaystyle \sum _{i=1}^{n}\pi _{i}p_{ij}=\pi _{j}.}$

تُعرَّف سلسلة ماركوف، كما سبق تعريفها، بأنها متوافقة مع الإزاحة من النوع المحدود إذا كان p_{_ij} = 0 عندما يكون A _{_ij} = 0. ويمكن تعريف مقياس ماركوف لمجموعة أسطوانية على النحو التالي:

${\displaystyle \mu (C_{t}[a_{0},\ldots ,a_{s}])=\pi _{a_{0}}p_{a_{0},a_{1}}\cdots p_{a_{s-1},a_{s}}}$

إنتروبيا كولموغوروف -سيناي وعلاقتها بمقياس ماركوف هي

${\displaystyle s_{\mu }=-\sum _{i=1}^{n}\pi _{i}\sum _{j=1}^{n}p_{ij}\log p_{ij}}$

مقاييس ماركوف وغير ماركوف

كما سبق، إذا توفرت لدينا مصفوفة انتقال ماركوف وتوزيع ثابت على الحالات، فيمكننا فرض مقياس احتمالي على الإزاحة الفرعية. على سبيل المثال، لننظر إلى سلسلة ماركوف الموضحة على اليسار على الحالات${\displaystyle A,B_{1},B_{2}}$، مع توزيع ثابت${\displaystyle \pi =(2/7,4/7,1/7)}$إذا "نسينا" التمييز بين${\displaystyle B_{1},B_{2}}$، نسقط هذا التحول الفرعي على${\displaystyle A,B_{1},B_{2}}$إلى وردية فرعية${\displaystyle A,B}$وهذا الإسقاط يُسقط أيضًا مقياس الاحتمالية إلى مقياس احتمالية على الإزاحة الفرعية على${\displaystyle A,B}$.

الأمر المثير للاهتمام هو أن مقياس الاحتمالية على التحول الفرعي على${\displaystyle A,B}$لا يتم إنشاؤها بواسطة سلسلة ماركوف على${\displaystyle A,B}$ولا حتى عدة طلبات. وبشكل بديهي، يرجع ذلك إلى أنه إذا لاحظ المرء سلسلة طويلة من${\displaystyle B^{n}}$عندها سيزداد يقين المرء بأن${\displaystyle Pr(A|B^{n})\to {\frac {2}{3}}}$وهذا يعني أن الجزء القابل للملاحظة من النظام يمكن أن يتأثر بشيء ما حدث في الماضي البعيد. ^{[ 4 ] [ 5 ]}

وعلى العكس من ذلك، يوجد إزاحة فرعية على 6 رموز، تم إسقاطها على إزاحة فرعية على رمزين، بحيث يكون لأي مقياس ماركوف على الإزاحة الفرعية الأصغر مقياس صورة عكسية ليس ماركوف من أي رتبة (مثال 2.6 ^{[ 5 ]} ).

تُعرَّف دالة زيتا لآرتين-مازور بأنها متسلسلة القوى الرسمية

${\displaystyle \zeta (z)=\exp \left(\sum _{n=1}^{\infty }{\Bigl |}{\textrm {Fix}}(T^{n}){\Bigr |}{\frac {z^{n}}{n}}\right),}$

حيث Fix( Tn ⁾ هي مجموعة النقاط الثابتة لعملية الإزاحة من الرتبة n . ^{[ 6 ]} ولها صيغة ضرب .

${\displaystyle \zeta (z)=\prod _{\gamma }\left(1-z^{|\gamma |}\right)^{-1}\ }$

حيث يمر γ عبر المدارات المغلقة. ^{[ 6 ]} بالنسبة للانزياحات الفرعية من النوع المحدود، فإن دالة زيتا هي دالة كسرية لـ z : ^{[ 7 ]}

${\displaystyle \zeta (z)=(\det(I-zA))^{-1}\ .}$

التحول السوفيكي هو صورة لتحول فرعي من النوع المحدود، حيث يمكن ربط حواف مختلفة من مخطط الانتقال بنفس الرمز. على سبيل المثال، إذا راقبنا فقط مخرجات سلسلة ماركوف المخفية، فستبدو المخرجات كنظام سوفيكي. ^{[ 4 ]} يمكن اعتباره مجموعة تصنيفات المسارات عبر آلة : التحول الفرعي من النوع المحدود يقابل آلة حتمية . ^{[ 8 ]} تتوافق هذه الأنظمة مع اللغات المنتظمة .

يتم تعريف الأنظمة الخالية من السياق بشكل مماثل، ويتم توليدها بواسطة قواعد بنية العبارة .

يُعرَّف نظام التجديد بأنه مجموعة جميع التسلسلات اللانهائية لمجموعة محدودة ثابتة من الكلمات المحدودة.

تُطابق التحولات الفرعية من النوع المحدود نماذج بوتس أحادية البعد الحرة (غير المتفاعلة) ( تعميمات من n حرفًا لنماذج إيزينغ )، مع استبعاد بعض التكوينات المجاورة. تُعرَّف نماذج إيزينغ المتفاعلة على أنها تحولات فرعية مصحوبة بدالة متصلة لفضاء التكوين (متصلة بالنسبة لطوبولوجيا الضرب، المُعرَّفة أدناه)؛ ويمكن التعبير عن دالة التقسيم والهاميلتوني بشكل صريح بدلالة هذه الدالة.

يمكن تكميم الإزاحات الفرعية بطريقة معينة، مما يؤدي إلى فكرة الأوتوماتا الكمومية المحدودة .

• مساحة الإزاحة
• موظف التحويل
• رسم بياني دي بروين
• الأوتوماتا الكمومية المحدودة
• البديهية أ
• تليف الرسوم البيانية

• برين، مايكل؛ ستوك، غاريت (2002). مقدمة في الأنظمة الديناميكية (  الطبعة الثانية). مطبعة جامعة كامبريدج . ISBN 0-521-80841-3.
• ديفيد دامانيك، التحولات الفرعية الإرجودية الصارمة والعوامل المرتبطة بها ، (2005)
• بيثياس فوج، ن. (2002). Berthé, فاليري ; فيرينزي، سيباستيان؛ مودويت، كريستيان؛ سيجل، أ. (محرران). البدائل في الديناميات والحساب والتوافقيات . ملاحظات محاضرة في الرياضيات. المجلد.  1794. برلين: سبرينغر-فيرلاغ . رقم ISBN 3-540-44141-7. Zbl 1014.11015 . 
• ناتاشا جونوسكا ، التحولات الفرعية من النوع المحدود، الأنظمة السوفية والرسوم البيانية ، (2000).
• مايكل س. كين، نظرية الإرجودية والتحولات الجزئية من النوع المحدود ، (1991)، يظهر كالفصل الثاني في كتاب نظرية الإرجودية، والديناميكا الرمزية، والفضاءات الزائدية ، تحرير تيم بيدفورد، ومايكل كين، وكارولين سيريز. مطبعة جامعة أكسفورد، أكسفورد (1991). ISBN 0-19-853390-X(يقدم مقدمة توضيحية قصيرة، مع تمارين ومراجع شاملة.)
• ليند، دوغلاس؛ ماركوس، برايان (1995). مقدمة في الديناميكيات الرمزية والترميز . مطبعة جامعة كامبريدج . ISBN 0-521-55124-2. Zbl 1106.37301 . 
• تيشل، جيرالد (2012). المعادلات التفاضلية العادية والأنظمة الديناميكية . بروفيدنس : الجمعية الرياضية الأمريكية . ISBN 978-0-8218-8328-0.
• شي، هويمين (1996). التعقيد النحوي والأنظمة الديناميكية أحادية البعد . اتجاهات في الفوضى. المجلد  6. وورلد ساينتيفيك. ISBN 9810223986.

• ويليامز، سوزان ج.، محررة. (2004). الديناميكا الرمزية وتطبيقاتها: الجمعية الأمريكية للرياضيات، دورة قصيرة، 4-5 يناير 2002، سان دييغو، كاليفورنيا . وقائع ندوات في الرياضيات التطبيقية: محاضرات الدورة القصيرة للجمعية الأمريكية للرياضيات. المجلد  60. الجمعية الأمريكية للرياضيات . ISBN 0-8218-3157-7. Zbl 1052.37003 .