• 検索結果がありません。

決定性オートマトンの隣接行列構造について――最小性の必要十分条件

N/A
N/A
Protected

Academic year: 2021

シェア "決定性オートマトンの隣接行列構造について――最小性の必要十分条件"

Copied!
1
0
0

読み込み中.... (全文を見る)

全文

(1)情報処理学会論文誌. プログラミング. Vol.7 No.5 16 (Dec. 2014). 発表概要. 決定性オートマトンの隣接行列構造について ——最小性の必要十分条件 新屋 良磨1,a) 2014年7月30日発表. 正規言語 L について,長さ–辞書順を用いた L と自然数の間の一対一対応を ranking と呼ぶ.正規言語 の ranking の計算は主に決定性オートマトンの隣接行列の冪の計算に帰着できる.我々はこれまで,正規 言語の ranking を用いた文字列圧縮の手法を提案してきた.本発表では,ranking の計算が効率的に行える 正規言語のクラスについて注目する.具体的には,数え上げ関数がきわめて単純なクラスである rank-one 言語:隣接行列の階数が 1 である決定性オートマトンで認識できる言語に注目する.一般に,同じ正規言 語を認識する等価な決定性オートマトンは無限に存在するため,正規言語 L が rank-one 性の判定のために L を認識する決定性オートマトンを列挙する手法は使えない.しかし,実際には最小オートマトンの階数 だけで rank-one 性を判定できることを説明する.実際には,最小オートマトンの隣接行列における rank と nullity が最小であることを示す.証明はオートマトン理論の道具である Nerode partition と スペクト ラルグラフ理論の道具である Equitable partition を用いる.. Graph Spectral Properties of Deterministic Finite Automata: A Necessary and Sufficient Condition for the Minimality Ryoma Sin’ya1,a) Presented: July 30, 2014. We prove that a minimal automaton has a minimal adjacency matrix rank and a minimal adjacency matrix nullity using equitable partition (from graph spectra theory) and Nerode partition (from automata theory). This result naturally introduces the notion of matrix rank into a regular language L, the minimal adjacency matrix rank of a deterministic automaton that recognises L.. 1. a). 東京工業大学大学院情報理工学研究科数理・計算科学専攻 Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Meguro, Tokyo 152–8552, Japan [email protected]. c 2014 Information Processing Society of Japan . 16.

(2)

参照

関連したドキュメント

This paper gives a decomposition of the characteristic polynomial of the adjacency matrix of the tree T (d, k, r) , obtained by attaching copies of B(d, k) to the vertices of

In this paper a similar problem is studied for semidynamical systems. We prove that a non-trivial, weakly minimal and negatively strongly invariant sets in a semidynamical system on

In Section 7, we classify the sets reduced decompositions which can correspond to paths between two flags in a semimodular lattice, and in Section 8, we use our results to derive

We also give some characterizations of 0-distributive semilattices and a characterization of minimal prime ideals containing an ideal of a 0-distributive

Our method of proof involves tracking the formation of the allelic partition using a certain Markov process, for which we prove a fluid limit.. Key words: Allelic

Since we need information about the D-th derivative of f it will be convenient for us that an asymptotic formula for an analytic function in the form of a sum of analytic

Giordano, Putnam and Skau introduced the notion of strong orbit equivalence for Cantor minimal systems in [GPS1], and showed that two systems are strong orbit equivalent if and only

Since congruence classes satisfy the condition in Theorem 4 and Algorithm 2 is just a special case of Algorithm 1, we know that Algorithm 2 terminates after a finite of steps and