Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Су́фіксний автома́т (англ. suffix automaton, directed acyclic word graph) — структура даних, що дозволяє зберігати в стислому вигляді і обробляти інформацію, пов'язану з підрядками одного рядка. Є детермінованим скінченним автоматом, який приймає всі суфікси слова і тільки їх, і що має найменшу можливу кількість станів серед всіх таких автоматів. Менш формально, суфіксний автомат — це орієнтований ациклічний граф з виділеною початковою вершиною і набором «фінальних» вершин, дуги якого позначені символами, такий що у будь-якої вершини символи на вихідних з неї дугах попарно різні і для будь-якого суфікса слова існує шлях з початкової вершини в деяку фінальну вершину, символи на якому при конкатенації утворюють даний суфікс. З усіх графів, які відповідають даним опису, суффіксним автоматом називається той, який володіє найменшим можливим числом вершин.
| Суфіксний автомат | ||
|---|---|---|
| Тип | Індекс підрядків | |
| Винайдено | 1983 | |
| Винайшли | Ансельм Блумер, Джанет Блумер, Анджей Еренфехт, Девід Хаусслер, Росс Макконнелл | |
| Обчислювальна складність у записі великого О | ||
| Середня | Найгірша | |
| Простір | ||
| Пошук | ||
| Вставляння | ||
| Видалення | ||
abbcbc.Суфіксний автомат був вперше описаний групою вчених з Денверського і Колорадського університетів в 1983 році, вони ж показали, що розмір автомата лінійно залежить від довжини , а також запропонували онлайн алгоритм для його побудови з лінійним часом роботи. У подальших роботах на цю тему був виявлений тісний зв'язок суфіксного автомата з суфікснимі деревами, а сама концепція суфіксного автомата отримала різні узагальнення. Так були введені стислий суфіксний автомат, який отримують із вихідного процедурою, аналогічною тій, яка застосовується до префіксного дерева для отримання суфіксного дерева, а також узагальнений суфіксний автомат, який будується для набору слів і приймає слова, які є суфіксами хоча б одного з цих.
За допомогою суфіксного автомата можна ефективно розв'зувати такі задачі як пошук підрядка в рядку, визначення найдовшого спільного підрядка двох і більше рядків тощо.
Застосування
Суфіксний автомат рядка 
може використовуватися для розв'язання таких задач, як:
- Підрахунок кількості різних підрядків
![image]()
за час ![image]()
в режимі онлайн, - Пошук найдовшого підрядка
![image]()
, що входить в неї хоча б два рази, за час ![image]()
, - Пошук найдовшого спільного підрядка рядків
![image]()
і ![image]()
за час ![image]()
, - Підрахунок кількості входжень рядка
![image]()
в ![image]()
в якості підрядка за час ![image]()
, - Пошук всіх входжень
![image]()
в ![image]()
за час ![image]()
, де ![image]()
— кількість входжень.
Тут варто вважати, що деякий рядок 
подається на вхід, коли автомат вже побудований і готовий до використання.
Суфіксні автомати також знайшли своє застосування в таких прикладних задачах, як стиснення даних, ідентифікація музики із записаних фрагментів і зіставлення геномних послідовностей.
Примітки
- Crochemore, Hancart, 1997, pp. 39—41
- Crochemore, Hancart, 1997, pp. 36—39
- Yamamoto et al., 2014, p. 675
- Crochemore et al., 2003, p. 211
- Mohri et al., 2009, p. 3553
- Faro, 2016, p. 145
Література
- Sgarbas K. N., Fakotakis N. D., Kokkinakis G. K. Optimal insertion in deterministic DAWGs // Theoretical Computer Science — Elsevier BV, 2003. — Vol. 301, Iss. 1-3. — P. 103–117. — ISSN 0304-3975; 1879-2294 — doi:10.1016/S0304-3975(02)00571-6
- Perrin D. Finite Automata // Formal Models and Semantics: Handbook of Theoretical Computer Science / J. v. Leeuwen — Elsevier BV, 1990. — Vol. B. — P. 1–57. — — doi:10.1016/B978-0-444-88074-1.50006-8
- Weiner P. Linear pattern matching algorithms // Symposium on Foundations of Computer Science — 1973. — P. 1–11. — 213 p. — doi:10.1109/SWAT.1973.13
- Pratt V. R. Improvements and applications for the Weiner repetition finder — 1973.
- Slisenko A. O. Detection of periodicities and string-matching in real time // Journal of Soviet mathematics — , 1983. — Vol. 22, Iss. 3. — P. 1316–1387. — ISSN 1072-3374; 1573-8795 — doi:10.1007/BF01084395
- Blumer A. C., Blumer J., Ehrenfeucht A. et al. Building the minimal DFA for the set of all subwords of a word on-line in linear time // Automata, Languages and Programming — 1984. — P. 109–118. — 526 p. — — doi:10.1007/3-540-13345-3_9
- Blumer A. C., Blumer J., Ehrenfeucht A. et al. Complete inverted files for efficient text retrieval and analysis // J. ACM / D. J. Rosenkrantz — New York, N.Y.: Association for Computing Machinery, 1987. — Vol. 34, Iss. 3. — P. 578–595. — ISSN 0004-5411 — doi:10.1145/28869.28873
- Blumer J. How much is that DAWG in the window? A moving window algorithm for the directed acyclic word graph // Journal of Algorithms — Academic Press, 1987. — Vol. 8, Iss. 4. — P. 451–469. — ISSN 0196-6774; 1090-2678 — doi:10.1016/0196-6774(87)90045-9
- Chen M., Seiferas J. Efficient and Elegant Subword-Tree Construction // Combinatorial Algorithms on Words / A. Apostolico, Z. Galil — Springer Berlin Heidelberg, 1985. — P. 97–107. — — doi:10.1007/978-3-642-82456-2_7
- Inenaga S. Bidirectional Construction of Suffix Trees // Nordic Journal of Computing — 2003. — Vol. 10, Iss. 1. — P. 52–67. — ISSN 1236-6064
- Mauri G. On-line construction of compact directed acyclic word graphs // Discrete Applied Mathematics — Elsevier BV, 2005. — Vol. 146, Iss. 2. — P. 156–179. — ISSN 0166-218X; 1872-6771 — doi:10.1016/J.DAM.2004.04.012
- Inenaga S., Hoshino H., Shinohara A. et al. Construction of the CDAWG for a trie // Prague Stringology Conference — Czech Technical University in Prague: 2001. — P. 37–48.
- Inenaga S., Shinohara A., Takeda M. et al. Compact directed acyclic word graphs for a sliding window // Journal of Discrete Algorithms — Elsevier BV, 2004. — Vol. 2, Iss. 1. — P. 33–51. — ISSN 1570-8667; 1570-8675 — doi:10.1016/S1570-8667(03)00064-9
- Yamamoto J., Tomohiro I, Bannai H. et al. Faster Compact On-Line Lempel-Ziv Factorization // Symposium on Theoretical Aspects of Computer Science / E. Mayr, N. Portier — 2014. — Vol. 25. — P. 675–686. — — ISSN 1868-8969 — doi:10.4230/LIPICS.STACS.2014.675
- Fujishige Y., Tsujimaru Y., Inenaga S. et al. Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets // Mathematical Foundations of Computer Science / P. Faliszewski, A. Muscholl, R. Niedermeier — 2016. — Vol. 58. — P. 38:1–38:14. — — ISSN 1868-8969 — doi:10.4230/LIPICS.MFCS.2016.38
- Mohri M., Moreno P., Weinstein E. General suffix automaton construction algorithm and space bounds // Theoretical Computer Science — Elsevier BV, 2009. — Vol. 410, Iss. 37. — P. 3553–3562. — ISSN 0304-3975; 1879-2294 — doi:10.1016/J.TCS.2009.03.034
- Faro S. Evaluation and Improvement of Fast Algorithms for Exact Matching on Genome Sequences // Algorithms for Computational Biology / M. Botón-Fernández, C. M. Vide, M. A. Vega-Rodríguez — Springer Nature Switzerland AG, 2016. — P. 145–157. — — doi:10.1007/978-3-319-38827-4_12
- Crochemore M., Hancart C. Automata for Matching Patterns // Handbook of Formal Languages / G. Rozenberg, A. Salomaa — Springer Berlin Heidelberg, 1997. — Vol. 2. — P. 399–462. — — doi:10.1007/978-3-662-07675-0_9
- Crochemore M., Vérin R. On compact directed acyclic word graphs // Structures in Logic and Computer Science: A Selection of Essays in Honor of A. Ehrenfeucht / J. Mycielski, G. Rozenberg, A. Salomaa — Springer Berlin Heidelberg, 1997. — P. 192–211. — — doi:10.1007/3-540-63246-8_12
- Crochemore M., Iliopoulos C. S., Navarro G. et al. A Bit-Parallel Suffix Automaton Approach for (δ,γ)-Matching in Music Retrieval // String Processing and Information Retrieval / M. A. Nascimento, Edleno S. de Moura, A. L. Oliveira — Springer Berlin Heidelberg, 2003. — P. 211–223. — — doi:10.1007/978-3-540-39984-1_16
- Hopcroft J. E., Ullman J. D. Introduction to Automata Theory, Languages, and Computation — 1 — MA: Addison-Wesley, 1979. — 418 p. —
- Fiala E. R., Greene D. H. Data compression with finite windows // Commun. ACM — [New York]: Association for Computing Machinery, 1989. — Vol. 32, Iss. 4. — P. 490–505. — ISSN 0001-0782; 1557-7317 — doi:10.1145/63334.63341
- Senft M., Dvořák T. Sliding CDAWG Perfection // String Processing and Information Retrieval / A. Turpin, A. Moffat, A. Amir — Springer Berlin Heidelberg, 2008. — P. 109–120. — — doi:10.1007/978-3-540-89097-3_12
- N. Jesper Larsson Extended application of suffix trees to data compression // Proceedings. Data Compression Conference — IEEE, 1996. — P. 190–199. — — ISSN 2375-0383; 2375-0391; 1068-0314; 2375-0359 — doi:10.1109/DCC.1996.488324
- Brodnik A., Jekovec M. Sliding Suffix Tree // Algorithms — MDPI, 2018. — Vol. 11, Iss. 8. — P. 118. — ISSN 1999-4893 — doi:10.3390/A11080118
- Rubinchik M., Shur A. M. Eertree: An efficient data structure for processing palindromes in strings // European Journal of Combinatorics / Patrice Ossona de Mendez, P. Rosenstiehl, Éric Colin de Verdière et al. — Elsevier BV, 2018. — Vol. 68. — P. 249–265. — ISSN 0195-6698; 1095-9971 — doi:10.1016/J.EJC.2017.07.021 — arXiv:1506.04862
- Серебряков В. А., Галочкин М. П., Фуругян М. Г. и др. Теория и реализация языков программирования: Учебное пособие — Москва: МЗ Пресс, 2006. — 352 с. —
- Рубцов А. А. Заметки и задачи о регулярных языках и конечных автоматах — Москва: МФТИ, 2019. — 112 с. —
- Паращенко Д. А. Обработка строк на основе суффиксных автоматов — СПб: ИТМО, 2007. — 35 с.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Su fiksnij avtoma t angl suffix automaton directed acyclic word graph struktura danih sho dozvolyaye zberigati v stislomu viglyadi i obroblyati informaciyu pov yazanu z pidryadkami odnogo ryadka Ye determinovanim skinchennim avtomatom yakij prijmaye vsi sufiksi slova S s 1 s 2 s n displaystyle S s 1 s 2 dots s n i tilki yih i sho maye najmenshu mozhlivu kilkist staniv sered vsih takih avtomativ Mensh formalno sufiksnij avtomat ce oriyentovanij aciklichnij graf z vidilenoyu pochatkovoyu vershinoyu i naborom finalnih vershin dugi yakogo poznacheni simvolami takij sho u bud yakoyi vershini simvoli na vihidnih z neyi dugah poparno rizni i dlya bud yakogo sufiksa slova S displaystyle S isnuye shlyah z pochatkovoyi vershini v deyaku finalnu vershinu simvoli na yakomu pri konkatenaciyi utvoryuyut danij sufiks Z usih grafiv yaki vidpovidayut danim opisu suffiksnim avtomatom nazivayetsya toj yakij volodiye najmenshim mozhlivim chislom vershin Sufiksnij avtomat Tip Indeks pidryadkiv Vinajdeno 1983 Vinajshli Anselm Blumer Dzhanet Blumer Andzhej Erenfeht Devid Haussler Ross Makkonnell Obchislyuvalna skladnist u zapisi velikogo O Serednya Najgirsha Prostir O n displaystyle O n O n displaystyle O n Poshuk Vstavlyannya Vidalennya Sufiksnij avtomat dlya abbcbc Sufiksnij avtomat buv vpershe opisanij grupoyu vchenih z Denverskogo i Koloradskogo universitetiv v 1983 roci voni zh pokazali sho rozmir avtomata linijno zalezhit vid dovzhini S displaystyle S a takozh zaproponuvali onlajn algoritm dlya jogo pobudovi z linijnim chasom roboti U podalshih robotah na cyu temu buv viyavlenij tisnij zv yazok sufiksnogo avtomata z sufiksnimi derevami a sama koncepciya sufiksnogo avtomata otrimala rizni uzagalnennya Tak buli vvedeni stislij sufiksnij avtomat yakij otrimuyut iz vihidnogo proceduroyu analogichnoyu tij yaka zastosovuyetsya do prefiksnogo dereva dlya otrimannya sufiksnogo dereva a takozh uzagalnenij sufiksnij avtomat yakij buduyetsya dlya naboru sliv S 1 S 2 S k displaystyle S 1 S 2 dots S k i prijmaye slova yaki ye sufiksami hocha b odnogo z cih Za dopomogoyu sufiksnogo avtomata mozhna efektivno rozv zuvati taki zadachi yak poshuk pidryadka v ryadku viznachennya najdovshogo spilnogo pidryadka dvoh i bilshe ryadkiv tosho ZastosuvannyaSufiksnij avtomat ryadka S displaystyle S mozhe vikoristovuvatisya dlya rozv yazannya takih zadach yak Pidrahunok kilkosti riznih pidryadkiv S displaystyle S za chas O S displaystyle O S v rezhimi onlajn Poshuk najdovshogo pidryadka S displaystyle S sho vhodit v neyi hocha b dva razi za chas O S displaystyle O S Poshuk najdovshogo spilnogo pidryadka ryadkiv S displaystyle S i T displaystyle T za chas O T displaystyle O T Pidrahunok kilkosti vhodzhen ryadka T displaystyle T v S displaystyle S v yakosti pidryadka za chas O T displaystyle O T Poshuk vsih vhodzhen T displaystyle T v S displaystyle S za chas O T k displaystyle O T k de k displaystyle k kilkist vhodzhen Tut varto vvazhati sho deyakij ryadok T displaystyle T podayetsya na vhid koli avtomat vzhe pobudovanij i gotovij do vikoristannya Sufiksni avtomati takozh znajshli svoye zastosuvannya v takih prikladnih zadachah yak stisnennya danih identifikaciya muziki iz zapisanih fragmentiv i zistavlennya genomnih poslidovnostej PrimitkiCrochemore Hancart 1997 pp 39 41 Crochemore Hancart 1997 pp 36 39 Yamamoto et al 2014 p 675 Crochemore et al 2003 p 211 Mohri et al 2009 p 3553 Faro 2016 p 145LiteraturaSgarbas K N Fakotakis N D Kokkinakis G K Optimal insertion in deterministic DAWGs Theoretical Computer Science Elsevier BV 2003 Vol 301 Iss 1 3 P 103 117 ISSN 0304 3975 1879 2294 doi 10 1016 S0304 3975 02 00571 6 d Track Q746413d Track Q7782354d Track Q99428232 Perrin D Finite Automata Formal Models and Semantics Handbook of Theoretical Computer Science J v Leeuwen Elsevier BV 1990 Vol B P 1 57 ISBN 978 0 444 88074 1 doi 10 1016 B978 0 444 88074 1 50006 8 d Track Q99428474d Track Q1812791d Track Q746413d Track Q99428342 Weiner P Linear pattern matching algorithms Symposium on Foundations of Computer Science 1973 P 1 11 213 p doi 10 1109 SWAT 1973 13 d Track Q29541479d Track Q72390208d Track Q7661883 Pratt V R Improvements and applications for the Weiner repetition finder 1973 d Track Q90300966d Track Q7917308 Slisenko A O Detection of periodicities and string matching in real time Journal of Soviet mathematics Springer Science Business Media 1983 Vol 22 Iss 3 P 1316 1387 ISSN 1072 3374 1573 8795 doi 10 1007 BF01084395 d Track Q176916d Track Q90305414d Track Q25999578d Track Q15760923 Blumer A C Blumer J Ehrenfeucht A et al Building the minimal DFA for the set of all subwords of a word on line in linear time Automata Languages and Programming 1984 P 109 118 526 p ISBN 978 3 540 13345 2 doi 10 1007 3 540 13345 3 9 d Track Q93055d Track Q66424197d Track Q6049376d Track Q89272679d Track Q92714d Track Q90309073 Blumer A C Blumer J Ehrenfeucht A et al Complete inverted files for efficient text retrieval and analysis J ACM D J Rosenkrantz New York N Y Association for Computing Machinery 1987 Vol 34 Iss 3 P 578 595 ISSN 0004 5411 doi 10 1145 28869 28873 d Track Q66424197d Track Q93055d Track Q90311855d Track Q92714d Track Q89272679d Track Q102353197d Track Q1709878 Blumer J How much is that DAWG in the window A moving window algorithm for the directed acyclic word graph Journal of Algorithms Academic Press 1987 Vol 8 Iss 4 P 451 469 ISSN 0196 6774 1090 2678 doi 10 1016 0196 6774 87 90045 9 d Track Q90327976d Track Q89272679d Track Q2076913d Track Q15757919 Chen M Seiferas J Efficient and Elegant Subword Tree Construction Combinatorial Algorithms on Words A Apostolico Z Galil Springer Berlin Heidelberg 1985 P 97 107 ISBN 978 3 642 82456 2 doi 10 1007 978 3 642 82456 2 7 d Track Q90329833d Track Q90333038d Track Q8075535d Track Q21541870d Track Q21587985 Inenaga S Bidirectional Construction of Suffix Trees Nordic Journal of Computing 2003 Vol 10 Iss 1 P 52 67 ISSN 1236 6064 d Track Q90336212d Track Q90335534 Mauri G On line construction of compact directed acyclic word graphs Discrete Applied Mathematics Elsevier BV 2005 Vol 146 Iss 2 P 156 179 ISSN 0166 218X 1872 6771 doi 10 1016 J DAM 2004 04 012 d Track Q5808319d Track Q54201216d Track Q57518591d Track Q746413 Inenaga S Hoshino H Shinohara A et al Construction of the CDAWG for a trie Prague Stringology Conference Czech Technical University in Prague 2001 P 37 48 d Track Q90341606d Track Q1329478d Track Q90342687 Inenaga S Shinohara A Takeda M et al Compact directed acyclic word graphs for a sliding window Journal of Discrete Algorithms Elsevier BV 2004 Vol 2 Iss 1 P 33 51 ISSN 1570 8667 1570 8675 doi 10 1016 S1570 8667 03 00064 9 d Track Q90345535d Track Q746413d Track Q15749817 Yamamoto J Tomohiro I Bannai H et al Faster Compact On Line Lempel Ziv Factorization Symposium on Theoretical Aspects of Computer Science E Mayr N Portier 2014 Vol 25 P 675 686 ISBN 978 3 939897 65 1 ISSN 1868 8969 doi 10 4230 LIPICS STACS 2014 675 d Track Q90351050d Track Q7661892d Track Q1359461d Track Q90348192 Fujishige Y Tsujimaru Y Inenaga S et al Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets Mathematical Foundations of Computer Science P Faliszewski A Muscholl R Niedermeier 2016 Vol 58 P 38 1 38 14 ISBN 978 3 95977 016 3 ISSN 1868 8969 doi 10 4230 LIPICS MFCS 2016 38 d Track Q90410044d Track Q90410566d Track Q65163370d Track Q28937052d Track Q90410629 Mohri M Moreno P Weinstein E General suffix automaton construction algorithm and space bounds Theoretical Computer Science Elsevier BV 2009 Vol 410 Iss 37 P 3553 3562 ISSN 0304 3975 1879 2294 doi 10 1016 J TCS 2009 03 034 d Track Q746413d Track Q7782354d Track Q90410808 Faro S Evaluation and Improvement of Fast Algorithms for Exact Matching on Genome Sequences Algorithms for Computational Biology M Boton Fernandez C M Vide M A Vega Rodriguez Springer Nature Switzerland AG 2016 P 145 157 ISBN 978 3 319 38827 4 doi 10 1007 978 3 319 38827 4 12 d Track Q21820634d Track Q90412453d Track Q90413024d Track Q90412338d Track Q90413187d Track Q62055857 Crochemore M Hancart C Automata for Matching Patterns Handbook of Formal Languages G Rozenberg A Salomaa Springer Berlin Heidelberg 1997 Vol 2 P 399 462 ISBN 978 3 642 59136 5 doi 10 1007 978 3 662 07675 0 9 d Track Q90413570d Track Q90413729d Track Q90413384d Track Q578300d Track Q21587985d Track Q5612543d Track Q29032892 Crochemore M Verin R On compact directed acyclic word graphs Structures in Logic and Computer Science A Selection of Essays in Honor of A Ehrenfeucht J Mycielski G Rozenberg A Salomaa Springer Berlin Heidelberg 1997 P 192 211 ISBN 978 3 540 69242 3 doi 10 1007 3 540 63246 8 12 d Track Q21587985d Track Q90413909d Track Q90414078d Track Q578300d Track Q505056d Track Q5612543d Track Q29032892d Track Q90413885 Crochemore M Iliopoulos C S Navarro G et al A Bit Parallel Suffix Automaton Approach for d g Matching in Music Retrieval String Processing and Information Retrieval M A Nascimento Edleno S de Moura A L Oliveira Springer Berlin Heidelberg 2003 P 211 223 ISBN 978 3 540 39984 1 doi 10 1007 978 3 540 39984 1 16 d Track Q90416626d Track Q90417045d Track Q90417771d Track Q90417529d Track Q90414195d Track Q21587985d Track Q28963131d Track Q63033736d Track Q90417285d Track Q29032892 Hopcroft J E Ullman J D Introduction to Automata Theory Languages and Computation 1 MA Addison Wesley 1979 418 p ISBN 978 81 7808 347 6 d Track Q90418603d Track Q771d Track Q62874d Track Q92794d Track Q353060 Fiala E R Greene D H Data compression with finite windows Commun ACM New York Association for Computing Machinery 1989 Vol 32 Iss 4 P 490 505 ISSN 0001 0782 1557 7317 doi 10 1145 63334 63341 d Track Q1120519d Track Q90425560 Senft M Dvorak T Sliding CDAWG Perfection String Processing and Information Retrieval A Turpin A Moffat A Amir Springer Berlin Heidelberg 2008 P 109 120 ISBN 978 3 540 89097 3 doi 10 1007 978 3 540 89097 3 12 d Track Q90416626d Track Q61745479d Track Q90426624d Track Q21587985d Track Q58612394d Track Q6603448 N Jesper Larsson Extended application of suffix trees to data compression Proceedings Data Compression Conference IEEE 1996 P 190 199 ISBN 0 8186 7358 3 ISSN 2375 0383 2375 0391 1068 0314 2375 0359 doi 10 1109 DCC 1996 488324 d Track Q102409399d Track Q90427112d Track Q131566d Track Q27726665 Brodnik A Jekovec M Sliding Suffix Tree Algorithms MDPI 2018 Vol 11 Iss 8 P 118 ISSN 1999 4893 doi 10 3390 A11080118 d Track Q4724371d Track Q48072239d Track Q90431355d Track Q90431196d Track Q30289533 Rubinchik M Shur A M Eertree An efficient data structure for processing palindromes in strings European Journal of Combinatorics Patrice Ossona de Mendez P Rosenstiehl Eric Colin de Verdiere et al Elsevier BV 2018 Vol 68 P 249 265 ISSN 0195 6698 1095 9971 doi 10 1016 J EJC 2017 07 021 arXiv 1506 04862 d Track Q746413d Track Q490790d Track Q21055200d Track Q5412712d Track Q3386861d Track Q90726647d Track Q98644576 Serebryakov V A Galochkin M P Furugyan M G i dr Teoriya i realizaciya yazykov programmirovaniya Uchebnoe posobie Moskva MZ Press 2006 352 s ISBN 5 94073 094 9 d Track Q90435122d Track Q90435415d Track Q90433200d Track Q649d Track Q90432456d Track Q90434687d Track Q21152579 Rubcov A A Zametki i zadachi o regulyarnyh yazykah i konechnyh avtomatah Moskva MFTI 2019 112 s ISBN 978 5 7417 0702 9 d Track Q90435728d Track Q649d Track Q1367256 Parashenko D A Obrabotka strok na osnove suffiksnyh avtomatov SPb ITMO 2007 35 s d Track Q656d Track Q90436837d Track Q1342013