正規表現研究の過去・現在・未来(2024 年版)

新屋, 良磨

doi:10.51094/jxiv.1017

##article.authors##

新屋, 良磨秋田大学　理工学部　数理科学コース

DOI:

https://doi.org/10.51094/jxiv.1017

キーワード:

オートマトン理論、形式言語理論、正規表現

抄録

本稿では，正規表現が誕生してから現在にいたるまでどのような研究が行われてきたのか，私見を交えつつ超駆け足で解説しようと思います．私の知識と紙面に限りがありますので，網羅的に解説することは不可能でして，個人的趣味による偏りの多い歴史解説になることをご容赦ください．特に，5節では2023年~2024年の国内の研究動向についてまとめてみました．日本の正規表現研究の今がいかに盛り上がってるかが伝わると幸いです．

利益相反に関する開示

開示すべき利益相反はありません

ダウンロード *前日までの集計結果を表示します

ダウンロード実績データは、公開の翌日以降に作成されます。

引用文献

Ada ́mek, J., Milius, S., Myers, R.S.R., Urbat, H.: Generalized Eilenberg Theorem I: Local varieties of languages. In: Foundations of Software Science and Computation Structures. pp. 366–380 (2014)

Chida, N., Terauchi, T.: Repairing regular expressions for extraction. In: Proceedings of the ACM on Programming Languages (Issue PLDI). vol. 7, pp. 1633–1656 (2023)

Conway, J.H.: Regular algebra and finite machines. Chapman and Hall (1971)

Eilenberg, S., Tilson, B.: Automata, languages and machines. Volume B. Pure and applied mathematics, Academic Press (1976)

Gehrke, M., Grigorieff, S., Pin, J.E ́.: A topological approach to recognition. In: Automata, Languages and Programming. pp. 151–162 (2010)

Inaba, K., Sin’ya, R., Nakamura, Y., Yamaguchi, Y.: Computational complexity of at-, pt- and gd-measurability for regular languages. In: The 26-th Workshop on Programming and Program- ming Langugaes (2024), (written in Japanese)

Kleene, S.C.: Representation of events in nerve nets and finite automata. RAND Corporation (1951), Project RAND Research Memorandum RM-704

Knuth, D.: Digital typography. CSLI Publications (1999)

Krob, D.: Complete systems ofb-rational identities. Theoretical Computer Science 89(2), 207– 343 (1991)

Lawson, M.V.: Finite Automata. Chapman and Hall/CRC (2003)

Leeuwen, J.V.: コンピュータ基礎理論ハンドブック形式的モデルと意味論, vol. II. 丸善出

版 (1994)

Mcculloch, W.S., Pitts, W.H.: A logical calculus of the ideas immanent in nervous activity.

Bulletin of Mathematical Biophysics 5, 115–133 (1943)

[13] Myhill, J.R.: Finite Automata and the Representation of Events. Tech. Rep. WADC TR-57-624, Wright-Paterson Air Force Base (1957)

Nakamura, Y.: Existential calculi of relations with transitive closure: Complexity and edge saturations. In: Logic in Computer Science. pp. 1–13. IEEE (2023)

Schu ̈tzenberger, M.: Sur le produit de concate ́nation non ambigu. Semigroup Forum 13, 47–75 (1976)

Schu ̈tzenberger,M.P.:Onfinitemonoidshavingonlytrivialsubgroups.InformationandControl (8), 190–194 (1965)

Simon, I.: Piecewise testable events. In: Automata Theory and Formal Languages. pp. 214–222 (1975)

Sin’ya, R.: Zero-One Law for Regular Languages. Ph.D. thesis, Tokyo Institute of Technology (2016)

Sin’ya, R.: Asymptotic approximation by regular languages. In: Current Trends in Theory and Practice of Computer Science. pp. 74–88 (2021)

Sin’ya, R.: Carathe ́odory extensions of subclasses of regular languages. In: Developments in Language Theory. pp. 355–367 (2021)

Sin’ya, R.: Measuring power of locally testable languages. In: Diekert, V., Volkov, M. (eds.) De- velopments in Language Theory. pp. 274–285. Springer International Publishing, Cham (2022)

Sin’ya, R.: Measuring power of generalised definite languages. In: Implementation and Appli- cation of Automata. pp. 278–289. Springer International Publishing (2023)

Thompson, K.: Programming techniques: Regular expression search algorithm. Commun. ACM 11(6), 419–422 (Jun 1968)

Turing, A.M.: On computable numbers, with an application to the entscheidungsproblem. Pro- ceedings of the London mathematical society 42(2), 230–265 (1936)

Uezato, Y.: Regular expressions with backreferences and lookaheads capture NLOG. In: Bringmann, K., Grohe, M., Puppis, G., Svensson, O. (eds.) 51st Interna- tional Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8- 12, 2024, Tallinn, Estonia. LIPIcs, vol. 297, pp. 155:1–155:20. Schloss Dagstuhl - Leibniz-Zentrum fu ̈r Informatik (2024). https://doi.org/10.4230/LIPICS.ICALP.2024.155, https://doi.org/10.4230/LIPIcs.ICALP.2024.155

Uramoto, T.: Semi-galois categories I: The classical Eilenberg variety theory. In: Logic in Com- puter Science. pp. 545–554 (2016)

Yuyama, T.: Groups whose word problems are accepted by abelian g-automata. In: Develop- ments in Language Theory. pp. 246–257. Cham (2023)

Yuyama, T. and Sin’ya, R.: Measuring power of commutative group languages. In: Implemen- tation and Application of Automata. pp. 347–362. Springer International Publishing (2024)

井上裕介, 橋本健二, 関浩之: 周期的な正則言語の巡回群による半直積分解. In: 第 26 回プログラミングおよびプログラミング言語ワークショップ (2024)

高橋和也, 南出靖彦: 拡張正規表現マッチングの計算量解析. コンピュータ・ソフトウェア 38(2), 53–70 (2021)

小林直樹: 高階モデル検査とその応用 (PPL サマースクール 2013 の講義スライド), http://www-kb.is.s.u-tokyo.ac.jp/ koba/ss2013/

新屋良磨: 正規表現に潜む対称性 ~ 等式公理による等価性判定 ~( 研究集会 SLACS2016 での招待講演スライド ) (2016), http://math.akita-u.ac.jp/ ̃ryoma/misc/slacs2016.pdf

新屋良磨: オートマトン理論再考. コンピュータ・ソフトウェア 34(3), 3–35 (2017)

新屋良磨, 山口勇太郎, 中村誠希: 部分語の出現情報の検査のみで近似できる正規言語につ

いて(PPL2022 推薦論文). コンピュータ・ソフトウェア 40(2), 49–60 (2023)

森畑明昌:先読み付き正規表現の有限状態オートマトンへの変換(PPL2011推薦論文)29(1),

–158 (2012)

田村孝行: 復刊半群論. 共立出版 (2001)

藤浪大弥: Redos 検出プログラム recheck の開発. In: 第 62 回プログラミング・シンポジウム (2021)

徳山豪・小林直樹(総編集): 理論計算機科学事典. 朝倉書店 (2022)

野上大成, 寺内多智弘: Regular expressions with backreferences on multiple context-free lan- guages, and star-closedness. In: 第 26 回プログラミングおよびプログラミング言語ワークショップ (2024)