著者

新屋 良磨

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.34, no.3, pp.3_3-3_35, 2017-07-25 (Released:2017-09-25)

---

オートマトンは最も単純な計算のモデルである.その単純さゆえに初学者にとっても理解しやすく,情報系の学部においては「計算理論」や「形式言語理論」などの講義はまずオートマトンから教え始めることが標準となっている.一方,その単純さゆえに理論的な深みやさらなる研究の余地がないと誤解されることもしばしばあり,また,講義や解説書においても応用的な需要からかより強力な計算モデルに重きが置かれることも多い.本サーベイではオートマトン理論の基礎から始め,三話構成でオートマトン・形式言語理論の様々な定理を解説していく.解説する定理の中には,オートマトン理論における古典的な結果に別の視点を新たに与えるものもあれば,オートマトン・形式言語理論と関わりのなさそうな分野との意外な繋がりを見せるものもある.オートマトン理論に習熟している方にも楽しんでもらえるよう,最近の結果や話題についても内容に盛り込んだ.

著者

新屋 良磨

出版者

一般社団法人 日本応用数理学会

雑誌

応用数理 (ISSN:24321982)

巻号頁・発行日

vol.31, no.4, pp.15-22, 2021-12-22 (Released:2022-03-31)

参考文献数

4

---

Formal language theory is the field of study of non-commutative objects so-called “languages” (sets of words). While many problems on languages are difficult to solve due to the non-commutativity, the situation could be drastically changed if we consider a commutative invariant of a language. This paper explains some commutative invariants of languages with concrete examples.

著者

新屋 良磨

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.36, no.4, pp.4_84-4_85, 2019-10-25 (Released:2019-12-25)

著者

新屋 良磨 山口 勇太郎 中村 誠希

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.40, no.2, pp.2_49-2_60, 2023-04-21 (Released:2023-06-21)

---

言語Lが正規可測であるとは,Lに「収束」する正規言語の対の無限列が存在することを言う.本論文では,正規言語の代わりに正規言語の部分クラスである区分検査可能(Piecewise Testable (PT): 部分語の出現情報の Bool 演算で記述可能)言語および文字検査可能(Alphabet Testable (AT): 文字の出現情報の Bool 演算で記述可能)言語に焦点を当てその可測性を考察する.特に,正規言語に対するAT可測性はco-NP完全である一方,PT可測性は線形時間で決定できることを示す.

著者

新屋 良磨

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.34, no.1, pp.1_119-1_124, 2017-01-25 (Released:2017-02-16)

---

与えられた言語が非正規であることの証明技法として,ポンピング補題や右同値類の有限性 (Myhill-Nerodeの定理) などの手法が有用であることが広く知られている.本論文ではこれらの手法とは全く異なる新しい非正規性の証明技法を提案する.いくつかの例題を通じて提案手法の新規性・有用性を議論し,さらに提案手法の課題についても具体的に述べる.提案技法は言語の測度に基づくものであり,「与えられた言語Lがほとんど空(測度が0)である」という直観的な性質を非正規性の証明に用いる.

著者

新屋 良磨 Shinya Ryoma

巻号頁・発行日

2016-03 (Released:2016-02-19)

著者

新屋 良磨

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.35, no.1, pp.1_82-1_85, 2018-01-25 (Released:2018-03-26)

著者

新屋 良磨 光成 滋生 佐々 政孝

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.30, no.2, pp.2_191-2_206, 2013-04-25 (Released:2013-08-25)

---

正規表現によるパターンマッチングは広く用いられており,これまで様々なマッチング手法が研究されてきた.正規表現をDFAに変換してマッチングを行う手法もその1つである.本論文では2つの高速化手法を提案する.1つ目の手法は,マッチングの並列化である.マッチング対象となる文字列を複数に分割してデータ並列にマッチング可能な,同時状態有限オートマトン(Simultaneous Finite Automata, SFA)をオートマトン理論の自然な拡張によって定義した.2つ目は,DFA・SFAから,ネイティブコードを実行時に最適化して生成する手法である.コード生成によって,既存実装に比べてマッチング時のスループットの向上が見込め,また特定の正規表現における最適化も可能となる.最終的に,これらの手法を実装し,マルチコアマシン上での評価を基にその有用性を確認した.

著者

新屋 良磨 Sin’ya Ryoma

出版者

秋田大学大学院理工学研究科

雑誌

秋田大学大学院理工学研究科研究報告 = SCIENTIFIC AND TECHNICAL REPORTS OF GRADUATE SCHOOL OF ENGINEERING SCIENCE, AKITA UNIVERSITY (ISSN:24324108)

巻号頁・発行日

vol.39, pp.15-22, 2018-11-30

---

Primitive word is a word that can not be represented by any repetition of shorter words. Since every nonempty word is a repetition of the unique primitive word, primitive words play an important role in combinatorics on words. In this article, we explain a long-standing open problem called “primitive words conjecture” which has a deep connection with the theory of context-free languages.

著者

新屋 良磨

出版者

日本ソフトウェア科学会 ; 1984-

雑誌

コンピュータソフトウェア = Computer software (ISSN:02896540)

巻号頁・発行日

vol.35, no.1, pp.82-85, 2018-02

著者

新屋 良磨

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.30, no.3, pp.3_163-3_179, 2013-07-25 (Released:2013-08-31)

---

Abstract Numeration System (ANS)は自然数と言語を一対一に対応づける記数法(Numeration System)である.本論文では,正規言語Lについて,Lに属する文字列wのL上のANSでの数 – wのL内での順番の計算によって圧縮を定義する.さらに,ANSによる圧縮では: (1) (無限集合である)正規言語Lから平均圧縮率を計算可能.(2) 圧縮対象の文字列長に対し準線形時間で圧縮可能.(3) 圧縮対象文字列wを分割して並列に圧縮可能等の良い性質を持つことを示す.本論文において,特に断らない限り任意長整数の乗算が定数時間で計算可能な一様コストモデルを仮定するが,乗算にコストがかかる場合での議論や解決策の提案も行う.