著者

大崎 人士

出版者

独立行政法人産業技術総合研究所

雑誌

若手研究(B)

巻号頁・発行日

2009

---

正則ACツリーオートマトン(regular AC-tree automata)の葉言語(leaf-languages)を表現する正則可換文法(commutative regular grammar)は、線形算術制約および正数ベクトル加算系(non-negative vector-addition systems)と等価な表現力を持つ(Parikh1966他)。本研究では、正数ベクトル加算系の定義を、整数(正値、零、負値)から成る座標系上に拡張した場合、それに対応する可換文法が満たすべき代数的性質を解明する。本研究の主な成果は、可換クリーニ代数の公理系に新たな演算子i と6つの公理を導入し(i-可換クリーニ代数と呼ぶ)、i-可換正規文法は、整数ベクトル加算系と等価な表現力を持つこと、正則可換文法、線形算術制約、正数ベクトル加算系の同形関係は、整数制約上へ自然に拡張可能であることが示せたことである。