Π£Π½ΠΈΠ²Π΅ΡΡΠ°Π»ΡΠ½ΡΠ΅ ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΡΡΠΈΠ΅ ΠΈ ΡΠ½ΠΈΠ²Π΅ΡΡΠ°Π»ΡΠ½ΡΠ΅ ΡΠΆΠΈΠΌΠ°ΡΡΠΈΠ΅ ΡΠ»ΠΎΠ²Π°
ΠΠΈΡΡΠ΅ΡΡΠ°ΡΠΈΡ
ΠΠ΅ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΠΠ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΠΎΠ²Π°Π½, Π½ΠΎ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΠΠ srf = (Q, E,<5) ΠΌΠΎΠΆΠ½ΠΎ ΡΠΊΠ°Π·Π°ΡΡ ΡΠ°Π½Π³ Π°Π²ΡΠΎΠΌΠ°ΡΠ° rk (#/) = min{|?(Q, Π³>)| v Π΅ Π*}. Π Π°Π½Π³ ΠΏΠΎΠΊΠ°Π·ΡΠ²Π°Π΅Ρ, ΠΊΠ°ΠΊΠΎΠ΅ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠΎΡΡΠΎΡΠ½ΠΈΠΉ ΠΌΠΎΠΆΠ΅Ρ ΠΏΠΎΠ»ΡΡΠΈΡΡΡΡ Π² ΠΎΠ±ΡΠ°Π·Π΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Q ΠΏΠΎΠ΄ Π΄Π΅ΠΉΡΡΠ²ΠΈΠ΅ΠΌ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ ΡΠ»ΠΎΠ²ΡΠ°ΠΊ, Π΄Π»Ρ ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΠ΅ΠΌΡΡ Π°Π²ΡΠΎΠΌΠ°ΡΠΎΠ² ΡΠ°Π½Π³ ΡΠ°Π²Π΅Π½ 1. ΠΠ°ΠΊ Π΄Π»Ρ ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΠ΅ΠΌΡΡ Π°Π²ΡΠΎΠΌΠ°ΡΠΎΠ², ΡΠ°ΠΊ ΠΈ Π΄Π»Ρ Π½Π΅ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΠ΅ΠΌΡΡ Π°Π²ΡΠΎΠΌΠ°ΡΠΎΠ² ΠΌΠΎΠΆΠ½ΠΎ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
- Π‘ΠΎΠ΄Π΅ΡΠΆΠ°Π½ΠΈΠ΅
- ΠΡΠ΄Π΅ΡΠΆΠΊΠ°
- ΠΠΈΡΠ΅ΡΠ°ΡΡΡΠ°
- ΠΡΡΠ³ΠΈΠ΅ ΡΠ°Π±ΠΎΡΡ
- ΠΠΎΠΌΠΎΡΡ Π² Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠΈ
Π‘ΠΎΠ΄Π΅ΡΠΆΠ°Π½ΠΈΠ΅
- ΠΠ²Π΅Π΄Π΅Π½ΠΈΠ΅
- 1. 1. Π‘ΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΠ΅ΠΌΠΎΡΡΡ ΠΈ ΡΠΆΠΈΠΌΠ°Π΅ΠΌΠΎΡΡΡ
- 1. 2. Π£Π½ΠΈΠ²Π΅ΡΡΠ°Π»ΡΠ½ΡΠ΅ ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΡΡΠΈΠ΅ ΡΠ»ΠΎΠ²Π°
- 1. 3. Π£Π½ΠΈΠ²Π΅ΡΡΠ°Π»ΡΠ½ΡΠ΅ ΡΠΆΠΈΠΌΠ°ΡΡΠΈΠ΅ ΡΠ»ΠΎΠ²Π°
- 1. 4. ΠΠΏΡΠΎΠ±Π°ΡΠΈΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠΎΠ²
- 2. Π Π°Π·ΡΠ΅ΡΠΈΠΌΠΎΡΡΡ Π·Π°Π΄Π°ΡΠΈ ΡΠ°ΡΠΏΠΎΠ·Π½Π°Π²Π°Π½ΠΈΡ ΡΠΆΠΈΠΌΠ°ΡΡΠΈΡ ΡΠ»ΠΎΠ²
- 3. ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠ°ΡΠΏΠΎΠ·Π½Π°Π²Π°Π½ΠΈΡ ΡΠΆΠΈΠΌΠ°ΡΡΠΈΡ
ΡΠ»ΠΎΠ²
- 3. 1. ΠΡΠ΅Π΄Π²Π°ΡΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ ΡΠ²Π΅Π΄Π΅Π½ΠΈΡ ΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ
- 3. 1. 1. Π€ΠΈΡΠΊΠΈ ΠΈ Π΄ΡΡΠΊΠΈ
- 3. 1. 2. ΠΠΎΡΠ»ΠΎΠΉΠ½ΠΎΠ΅ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΠ΅
- 3. 1. 3. Π‘ΡΡΠΎΠ΅Π½ΠΈΠ΅ ΡΠ»ΠΎΡ
- 3. 1. 4. Π‘ΡΡΠΎΠ΅Π½ΠΈΠ΅ ΡΠ»ΠΎΡ ΠΏ-ΡΠΎΠ±ΡΡΠ²Π΅Π½Π½ΠΎΠ³ΠΎ Π°Π²ΡΠΎΠΌΠ°ΡΠ°
- 3. 1. 5. ΠΠ΅ΡΠΊΠΈ ΡΠΎΡΡΠΎΡΠ½ΠΈΠΉ ΠΈ ΡΠΎΠ»ΠΈ Π±ΡΠΊΠ²
- 3. 1. 6. ΠΡΠ½ΠΎΠ²Π°
- 3. 1. 7. ΠΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΠΏΠΎ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΡ ΠΎΡΠ½ΠΎΠ²Ρ
- 3. 1. 8. ΠΡΡΠΈΡΠ»Π΅Π½ΠΈΡ ΠΏΠΎ ΠΎΡΠ½ΠΎΠ²Π΅
- 3. 2. ΠΠ»Π³ΠΎΡΠΈΡΠΌ
- 3. 2. 1. ΠΠ±ΡΠ΅Π΅ ΠΎΠΏΠΈΡΠ°Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°
- 3. 2. 2. ΠΡΠΎΠ²Π΅ΡΠΊΠ° ΡΠ»ΠΎΠ²Π° Π½Π° ΠΏ-ΠΏΠΎΠ»Π½ΠΎΡΡ
- 3. 2. 3. ΠΠ΅Π½Π΅ΡΠ°ΡΠΈΡ ΡΠΎΠ»Π΅ΠΉ Π±ΡΠΊΠ²
- 3. 2. 4. Π Π°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΡΠΎΠ»Π΅ΠΉ ΠΈ Π½Π°ΡΠ°Π»ΠΎ ΡΠ΅ΠΊΡΡΡΠΈΠΈ
- 3. 2. 5. Π¨Π°Π³ ΡΠ΅ΠΊΡΡΡΠΈΠΈ (ΡΠ°Π·Π±ΠΈΠ΅Π½ΠΈΠ΅ Π½Π° ΠΏΠΎΠ΄ΠΊΠ»Π°ΡΡΡ)
- 3. 2. 6. ΠΠ»Π°ΡΡΡ Π°Π²ΡΠΎΠΌΠ°ΡΠΎΠ², Π½Π΅ ΡΡΠ΅Π±ΡΡΡΠΈΠ΅ ΡΠ°Π·Π±ΠΈΠ΅Π½ΠΈΡ
- 3. 2. 7. ΠΠΎΡΡΠ΅ΠΊΡΠ½ΠΎΡΡΡ
- 3. 3. ΠΠ΅ΠΈΠ·ΠΎΠΌΠΎΡΡΠ½ΠΎΡΡΡ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΠΌΡΡ Π°Π²ΡΠΎΠΌΠ°ΡΠΎΠ²
- 3. 4. ΠΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°
- 3. 1. ΠΡΠ΅Π΄Π²Π°ΡΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ ΡΠ²Π΅Π΄Π΅Π½ΠΈΡ ΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ
- 4. ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ ΠΏΠΎΠΈΡΠΊΠ° ΠΈ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΡΠΈΠ½Ρ
ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΡΡΠΈΡ
ΠΈ ΡΠΆΠΈΠΌΠ°ΡΡΠΈΡ
ΡΠ»ΠΎΠ²
- 4. 1. ΠΠ΅ΡΠ΅Π±ΠΎΡΠ½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠΈΡΠΊΠ° ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΡ ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΡΡΠΈΡ ΡΠ»ΠΎΠ²
- 4. 2. ΠΠΎΠΈΡΠΊ ΡΠΆΠΈΠΌΠ°ΡΡΠΈΡ ΡΠ»ΠΎΠ²
- 4. 3. Π Π°ΡΠΏΠΎΠ·Π½Π°Π²Π°ΡΠ΅Π»Ρ ΡΠ»ΠΎΠ², ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΡΡΠΈΡ Π°Π²ΡΠΎΠΌΠ°Ρ
- 4. 4. ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΡΡΠΈΡ ΡΠ»ΠΎΠ² ΡΠ΅ΡΠ΅Π· ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΡΠ·ΡΠΊΠΎΠ²
- 4. 5. Π Π΅Π·ΡΠ»ΡΡΠ°ΡΡ
- 5. ΠΠ΅ΡΠΊΠ°Π»ΡΠ½ΡΠΉ ΠΎΠ±ΡΠ°Π· 2-ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΡΡΠΈΡ ΡΠ»ΠΎΠ²
Π‘ΠΏΠΈΡΠΎΠΊ Π»ΠΈΡΠ΅ΡΠ°ΡΡΡΡ
- ΠΠ»ΡΡΠΊΠΎ Π.Π., Π ΡΡΡΠΎΠ² Π. Π., Π‘ΠΏΠΈΠ²Π°ΠΊ Π. Π. ΠΠΊΡΡΡΠ΅ΠΌΠ°Π»ΡΠ½Π°Ρ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΎΡΠ½Π°Ρ Π·Π°Π΄Π°ΡΠ°, ΡΠ²ΡΠ·Π°Π½Π½Π°Ρ Ρ Π΄Π»ΠΈΠ½ΠΎΠΉ ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΡΡΠ΅Π³ΠΎ ΡΠ»ΠΎΠ²Π° Π² Π°Π²ΡΠΎΠΌΠ°ΡΠ΅ / / ΠΠΈ-Π±Π΅ΡΠ½Π΅Π½ΠΈΠΊΠ°. 1987. № 2. Π‘. 16−20.
- ΠΠ°ΡΡΡΠ³ΠΈΠ½ Π.Π. ΠΠ΅ΡΠ΅ΠΆΠ½Π°Ρ ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΠ΅ΠΌΠΎΡΡΡ ΡΠ°ΡΡΠΈΡΠ½ΡΡ Π°Π²ΡΠΎΠΌΠ°ΡΠΎΠ² // Π’ΡΡΠ΄Ρ 39-ΠΉ ΡΠ΅Π³ΠΈΠΎΠ½Π°Π»ΡΠ½ΠΎΠΉ ΠΌΠΎΠ»ΠΎΠ΄Π΅ΠΆΠ½ΠΎΠΉ ΠΊΠΎΠ½ΡΠ΅ΡΠ΅Π½ΡΠΈΠΈ «ΠΡΠΎΠ±Π»Π΅ΠΌΡ ΡΠ΅ΠΎΡΠ΅ΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΠΈ ΠΏΡΠΈΠΊΠ»Π°Π΄Π½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠΈ». ΠΠΊΠ°ΡΠ΅ΡΠΈΠ½Π±ΡΡΠ³, 2008. Π‘. 336−341.
- ΠΠ°ΡΡΡΠ³ΠΈΠ½ Π.Π. ΠΠΈΠΆΠ½ΠΈΠ΅ ΠΎΡΠ΅Π½ΠΊΠΈ Π΄Π»ΠΈΠ½Ρ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΡ Π±Π΅ΡΠ΅ΠΆΠ½ΠΎ ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΡΡΠΈΡ ΡΠ»ΠΎΠ² Π΄Π»Ρ Π΄Π²ΡΡ - ΠΈ ΡΡΡΡ Π±ΡΠΊΠ²Π΅Π½Π½ΡΡ ΡΠ°ΡΡΠΈΡΠ½ΡΡ Π°Π²ΡΠΎΠΌΠ°ΡΠΎΠ² // ΠΠΈΡΠΊΡΠ΅ΡΠ½ΡΠΉ Π°Π½Π°Π»ΠΈΠ· ΠΈ ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ. 2008. Π‘. 44−56.
- ΠΠ°ΡΡΡΠ³ΠΈΠ½ Π.Π. PSPACE-ΠΏΠΎΠ»Π½ΠΎΡΠ° Π·Π°Π΄Π°ΡΠΈ ΠΏΡΠΎΠ²Π΅ΡΠΊΠΈ ΡΠ°ΡΡΠΈΡΠ½ΡΡ Π°Π²ΡΠΎΠΌΠ°ΡΠΎΠ² Π½Π° Π±Π΅ΡΠ΅ΠΆΠ½ΡΡ ΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·ΠΈΡΡΠ΅ΠΌΠΎΡΡΡ // ΠΠ·Π²Π΅ΡΡΠΈΡ Π£ΡΠ°Π»ΡΡΠΊΠΎΠ³ΠΎ Π³ΠΎΡΡΠ΄Π°ΡΡΡΠ²Π΅Π½Π½ΠΎΠ³ΠΎ ΡΠ½ΠΈΠ²Π΅ΡΡΠΈΡΠ΅ΡΠ°. 2008. № 62. Π‘. 106−150.
- Π ΡΡΡΠΎΠ² Π.Π. Π Π΄Π»ΠΈΠ½Π΅ Π²ΠΎΠ·Π²ΡΠ°ΡΠ½ΡΡ ΡΠ»ΠΎΠ² Π΄Π»Ρ Π°Π²ΡΠΎΠΌΠ°ΡΠΎΠ² Ρ ΠΏΡΠΎΡΡΡΠΌΠΈ ΠΈΠ΄Π΅ΠΌ-ΠΏΠΎΡΠ΅Π½ΡΠ°ΠΌΠΈ // ΠΠΈΠ±Π΅ΡΠ½Π΅ΡΠΈΠΊΠ° ΠΈ ΡΠΈΡΡΠ΅ΠΌΠ½ΡΠΉ Π°Π½Π°Π»ΠΈΠ·. 2000. № 3. Π‘. 32−39.
- Π₯ΠΎΠΏΠΊΡΠΎΡΡ ΠΠΆ. ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π΄Π»Ρ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°ΡΠΈΠΈ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ³ΠΎ Π°Π²ΡΠΎΠΌΠ°ΡΠ° // ΠΠΈΠ±Π΅ΡΠ½Π΅ΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΡΠ±ΠΎΡΠ½ΠΈΠΊ. ΠΠΎΠ²Π°Ρ ΡΠ΅ΡΠΈΡ. Π.: ΠΠΈΡ, 1974. ΠΡΠΏ. 11. Π‘. 177−184.
- Programmable and autonomus computing machine made of biomolecules / R. Adar, Y. Benenson, E. Keinan et al.] // Nature. Vol. 414 № 1. P. 430−434.
- DNA molecule provides a computing machine with both data and fuel / R. Adar, Y. Benenson, Z. Livneh et al.] // Proceedings of the National Academy of Sciences of USA. 2003. Vol. 100. P. 2191−2196.
- Almeida J., Volkov M.V. Profinite identities for finite semigroups whose subgroups belong to a given pseudovariety // Journal of Algebra and Its Applications. 2003. № 2. P. 137−163.
- Almeida J., Volkov M.V. Subword complexity of profinite words and subgroups of free profinite semigroups // International Journal of Algebra and Computation. 2006. Vol. 15 № 2. P. 221−258.
- Ananichev D.S., Cherubini A., Volkov M.V. Image reducing words and subgroups of free groups // Theoretical Computer Science. 2003. Vol. 307. P. 77−92.
- Ananichev D.S., Volkov M.V. Synchronizing monotonic automata // Lecture Notes in Computer Science: Developments in Language Theory (7th International Conference, Szeged, 2003). Berlin-Heidelberg-New York: Springer-Verlag, 2003. Vol. 2710. P. 111−121.
- Cerny J. Poznamka ΠΊ homogennym eksperimentom s konecnymi avtomatami // Matematicko-Fyzikalny Casopis. Slovenskej Akademie Vied, 1964. Vol. 14. P. 208−216.
- Cherubini A., Kisielewicz A. Recognizing collapsing words is co-NP-complete // Proceedings of the 8th International Workshop on Descriptional Complexity of Formal Systems / Eds. H. Leung, G. Pighizzini. Las Cruces, 2006. P. 106−117.
- Cherubini A., Kisielewicz A. Collapsing words, permutation conditions and coherent colorings of trees // Theoretical Computer Science. 2009. Vol. 410. P. 2135−2147.
- Dubuc L. Sur les automates circulaires et la conjecture de Cerny // RAIRO Theoretical Informatics and Application. 1998. Vol. 32. P. 21−34.
- Duske J., Ito M. On cofinal and definite automata // Acta Cybernetica. 1983. Vol. 6. P. 181−189.
- Eppstein D. Reset sequences for monotonic automata / / SI AM Journal on Computing. 1990. Vol. 19. P. 500−510.
- Jurgensen H. Synchronization. // Proceedings of International Conference on Language and Automata Theory and Applications. Tarragona, 2007. P. 27−49.
- Kari J. A counter example to a conjecture concerning synchronizing words in finite automata // EATCS Bull. 2001. Vol. 73. P. 146.
- Margolis S., Pin J.-E., Volkov M.V. Words guaranteeing minimum image // International Journal of Foundations of Computer Science. 2004. Vol. 15. P. 259−276.
- Martyugin P.V. Complexity of problems concerning reset words for commutative automata and automata with simple idempotents / / Proceedings of the 12th International Conference on Automata and Formal Languages. 2008. P. 314−324.
- Martyugin P.V. A series of slowly synchronizable automata with a zero state over a small alphabet // Information and Computation. 2008. Vol. 206. P. 1197−1203.
- Moore E. Gedanken-experiments with sequential machines // Annals of Mathematics Studies: Automata Studies / Eds. Π‘. E. Shannon, J. McCarthy. Princeton: Princeton University Press, 1956. № 34. P. 129−153.
- Natarajan B.K. An algorithmic approach to the automated design of parts orienters // Foundations of Computer Science: 27th Annual Symposium. IEEE, 1986. P. 132−142.
- Pin J.-E. On two combinatorial problems arising from automata theory // Annals of Discrete Mathematics. 1983. Vol. 17. P. 535−548.
- Identities in full transformation semigroups. / R. Poschel, M.V. Sapir, N. Sauer et al.] //Algebra Universalis. 1994. Vol. 31. P. 580−588.
- Pribavkina E.V. On some properties of the Language of 2-collapsing words // International Journal of Foundations of Computer Science. 2006. Vol. 17. P. 665−676.
- Reilly N.R., Zhang S. Decomposition of the lattice of pseudovarieties of finite semigroups induced by bands //Algebra Universalis. 2000. Vol. 44. P. 217−239.
- Rystsov I.C. Reset words for commutative and solvable automata // Theoretical Computer Science. 1997. Vol. 172. P. 273−279.
- Salomaa A. Composition sequences for functions over a finite domain. // Theoretical Computer Science. 2003. Vol. 292. P. 263−281.
- Samotij W. A note on the complexity of the problem of finding shortest synchronizing words // Proceedings of International Conference AutoMathA. Palermo, 2007.
- Sauer N., Stone M.G. Composing functions to reduce image size // Ars Combinatoria. 1991. Vol. 31. P. 171−176.
- Trahtman A.N. The Cerny conjecture for aperiodic automata // Discrete Mathematics and Theoretical Computer Science. 2007. Vol. 9 № 2. P. 3−10.
- Π Π°Π±ΠΎΡΡ Π°Π²ΡΠΎΡΠ° ΠΏΠΎ ΡΠ΅ΠΌΠ΅ Π΄ΠΈΡΡΠ΅ΡΡΠ°ΡΠΈΠΈ
- Ananichev D.S., Petrov I.V., Volkov M.V. Collapsing words: a progress report // International Journal of Foundations of Computer Science. 2006. Vol. 17 № 3. P. 507−518.
- Petrov I.V. An algorithm for recognition of n-collapsing words // Theoretical Computer Science. 2008. Vol. 391. P. 99−108.