講演名	2001/7/17 P/Tペトリネットの行列方程式の非負整数非同次解のgeneratorの導出 : 拡大接続行列の有理数基底からの導出 高田 真樹, 松本 忠, 茂呂 征一郎,
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)	P/Tペトリネットの行列方程式Ax=b(A⋳Z^b⋳Z^)の任意の非負整数非同次解は, レベル6では最も簡単な形式(極小T-インバリアントの非負整数重みつき一次結合と非負整数特解1個の和(但し, 非負整数特解は一般に複数個存在する))で表現でき, 可到達時間を考える上で最も有用であると思われる。そこで, これらのgeneratorを効率よく導出する方法が必要である.その導出法には, 拡大接続行列から直接的に導出する方法と拡大接続行列からレベル3以下の解のgeneratorを求めて, そのgeneratorからレベル6の解のgenerator(U_6, V_6)を導出する間接的な方法がある.間接的な方法としては, スミス・エルミート正準形から得られるレベル2のAx=0^に対する解のgenerator U_2(拡大接続行列の整数基底)から導出する方法とLP表現の端点探索法から得られるレベル3のAx=0^に対する解のgeneratorU_3(拡大接続行列の非負有理数基底)から導出する方法がある.本論文では, レベル1のAx=0^に対する解のgenerator U_1がガウスの消去法や閉形解から容易に得られることを利用しPU_1からレベル6のAx=bに対する解のgenerator(U_6, V_6)を同時に導出する方法を示している.また, U_1からレベル2のAx=0^に対する解のgenerator U_2(従って, Ax=bに対する解のgenerator(U_2, V_2))を導出する方法とU_1からレベル3のAx=0^に対する解のgeneratorU_3(従って, Ax=bに対する解のgenerator(U_3, V_3)を導出する方法も示している.
抄録(英)	An arbitrary nonnegative integer solution of matrix equation of P/T Petri net systems is expressed at level 6 by the sum of a nonnegative integer particular solution (however, note that there exist in general more than one particular solution) and a nonnegative homogeneous solution which is a linear combination of all minimal T-invariants where each coefficient is also nonnegative integer. Then, it is hoped to establish efficient generation methods for V_6(i.e., all nonnegative integer particular solutions)and U_6(i.e., all minimal T-invariants). In this paper, a new algorithm for (U_6, V_6) starting from Q^-basis(i.e., the augmented level-1 generator for Ax=0^U_1={u_1⋳Q^<(n+1)×1>|Au_i=0^i⋳I(n+1-r)}) is proposed, where A:=[A, -b]⋳Z^r:=rank(A)=rank(A), and U_1 is easily obtained by Gaussian elimination algorithm or algebraic closed form formula for Ax=0^. We also propose the algorithm for U_2 starting from Q^-basis and the algorithm for U_3 starting from Q^<(n+1)×1>-basis.
キーワード(和)	ペトリネット / 行列方程式 / 発火回数ベクトル / インバリアント / 非負整数基本特解 / 可到達問題
キーワード(英)	Petri nets / matrix equations / firing count vectors / invariants / nonnegative integer basic particular solutions / reachability
資料番号	CST2001-13
発行日

研究会情報
研究会	CST
開催期間	2001/7/17(から1日開催)
開催地（和）
開催地（英）
テーマ（和）
テーマ（英）
委員長氏名（和）
委員長氏名（英）
副委員長氏名（和）
副委員長氏名（英）
幹事氏名（和）
幹事氏名（英）
幹事補佐氏名（和）
幹事補佐氏名（英）

講演論文情報詳細
申込み研究会	Concurrent System Technology (CST)
本文の言語	ENG
タイトル（和）	P/Tペトリネットの行列方程式の非負整数非同次解のgeneratorの導出 : 拡大接続行列の有理数基底からの導出
サブタイトル（和）
タイトル（英）	A New Algorithm to Derive Generators of Matrix Equations for P/T Petri Nets : A Method via Q-basis for Augmented Incidence Matrix
サブタイトル（和）
キーワード(1)（和/英）	ペトリネット / Petri nets
キーワード(2)（和/英）	行列方程式 / matrix equations
キーワード(3)（和/英）	発火回数ベクトル / firing count vectors
キーワード(4)（和/英）	インバリアント / invariants
キーワード(5)（和/英）	非負整数基本特解 / nonnegative integer basic particular solutions
キーワード(6)（和/英）	可到達問題 / reachability
第 1 著者 氏名（和/英）	高田 真樹 / Maki TAKATA
第 1 著者 所属（和/英）	福井大学 工学部 電気・電子工学科 Dept.of Electrical and Electronics Engineering, Faculty of Engineering, Fukui University
第 2 著者 氏名（和/英）	松本 忠 / Tadashi MATSUMOTO
第 2 著者 所属（和/英）	福井大学 工学部 電気・電子工学科 Dept.of Electrical and Electronics Engineering, Faculty of Engineering, Fukui University
第 3 著者 氏名（和/英）	茂呂 征一郎 / Seiichiro MORO
第 3 著者 所属（和/英）	福井大学 工学部 電気・電子工学科 Dept.of Electrical and Electronics Engineering, Faculty of Engineering, Fukui University
発表年月日	2001/7/17
資料番号	CST2001-13
巻番号（vol）	vol.101
号番号（no）	212
ページ範囲	pp.-
ページ数	8
発行日