| Item type |
SIG Technical Reports(1) |
| 公開日 |
2021-08-18 |
| タイトル |
|
|
タイトル |
オートマトンを用いたあみだくじの列挙 |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
東北大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
東北大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
東北大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
東北大学大学院情報科学研究科 |
| 著者所属(英) |
|
|
|
en |
|
|
GSIS, Tohoku University |
| 著者所属(英) |
|
|
|
en |
|
|
GSIS, Tohoku University |
| 著者所属(英) |
|
|
|
en |
|
|
GSIS, Tohoku University |
| 著者所属(英) |
|
|
|
en |
|
|
GSIS, Tohoku University |
| 著者名 |
熊谷, 滉士郎
ディプタラマ, ヘンリアン
吉仲, 亮
篠原, 歩
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
無限集合の要素を列挙するのは不可能であるが，これらを適切な方法で符号化した文字列を受理する決定性オートマトン (DFA) を構築することで，目標の無限集合の要素の列挙と見なすことができる．本発表では縦線数 n のあみだくじを符号化した文字列からなるあみだくじ言語を受理する DFA を提案する．この DFA は O(4n) 時間で構築可能であり，我々は n = 30 まで実際に求めることができた．さらにあみだくじを拡張し，最左の縦線と最右の縦線が隣り合っているとみなして横線を引くことを許す循環あみだくじを定義する．循環あみだくじ言語を受理する DFA は O(4nn2) 時間で構築可能であるが，循環あみだくじにおける縦線の対称性に着目して状態数を大幅に減らすことで n = 32 までの構築に成功した． |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2021-AL-184,
号 6,
p. 1-8,
発行日 2021-08-18
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL21184006.pdf (823.9 kB)
