Preprint / Version 1

Studies on Regular Expressions: past, present and future

##article.authors##

  • Ryoma Sin'ya Mathematical Science Course, Akita University

DOI:

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

Keywords:

Automata, Formal Languages, Regular Expressions

Abstract

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

Conflicts of Interest Disclosure

The author declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Downloads *Displays the aggregated results up to the previous day.

Download data is not yet available.

References

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)

Downloads

Posted


Submitted: 2024-12-31 08:48:25 UTC

Published: 2025-02-26 06:52:23 UTC
Section
Information Sciences

License

Copyright (c) 2025 Ryoma Sin'ya

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.