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

Counting for Recognizable and Algebraic Series

N/A
N/A
Protected

Academic year: 2021

シェア "Counting for Recognizable and Algebraic Series"

Copied!
1
0
0

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

全文

(1)情報処理学会論文誌. プログラミング. Vol.10 No.5 4 (Nov. 2017). 発表概要. Counting for Recognizable and Algebraic Series 関 浩之1,a). 橋本 健二1,b). Trung Chu Bao1,c). 2017年3月3日発表. 与えられた制約を満たす文字列の計数問題は,文字列を扱うプログラムの脆弱性解析に応用できること から注目されている.本発表では,形式級数の計数問題について議論する.形式級数とは,語に係数(ま たは重み)とよばれる値を関連づけることによって形式言語を拡張したものである.特に,認識可能級数 と代数的級数はそれぞれ正則言語と文脈自由言語の拡張である.形式級数 S と自然数 n に対し,長さ n の 語の S における重み和を CC (S, n),長さ n で S における重みが非零の語数を SC (S, n) と表す.本発表 ではまず,与えられた認識可能級数 S と自然数 n に対し,CC (S, n) は O(k log n) で計算できることを示 す.ここで,k は S における 1 回の状態遷移行列演算に要する時間である.また,S における状態遷移行 列が乗算に関して可換であるとき,SC (S, n) は n の多項式時間で計算できることを示す.次に,上記 2 つ の問題を形式木級数にも定義し,それらの計算法を論ずる.最後に,代数的級数 S に対して動的計画法に より CC (S, n) を O(n2 ) 時間で計算する方法を示す.. Counting for Recognizable and Algebraic Series Hiroyuki Seki1,a). Kenji Hashimoto1,b). Trung Chu Bao1,c). Presented: March 3, 2017. Counting problems for strings that satisfy given constraints are paid an attention because string counting methods can be applied to the vulnerability analysis of programs that deal with strings. In this presentation, we discuss counting problems for formal series. Formal series are a natural extension of formal languages by associating each word with a value called a coefficient or a weight. Among them, recognizable series and algebraic series can be regarded as extensions of regular languages and context-free languages, respectively. For a formal series S and a natural number n, let CC (S, n) denote the sum of the coefficients of all the words of length n in S and SS (S, n) the number of words of length n that have non-zero coefficients in S. We show that for a given recognizable series S and a natural number n, CC (S, n) can be computed in O(k log n) time where k is an upper-bound of time needed for a single state-transition matrix operation, and if the state-transition matrices of S are commutative for multiplication, SC (S, n) can be computed in polynomial time of n. We also extend the notions to tree series and discuss how to compute them efficiently. Finally, we propose an algorithm that computes CC (S, n) in O(n2 ) time for an algebraic series S.. 1 a) b) c). 名古屋大学 Nagoya University, Nagoya, Aichi 464–8601, Japan [email protected] [email protected] [email protected]. c 2017 Information Processing Society of Japan . 4.

(2)

参照

関連したドキュメント

581] asserts the existence for any natural number N of a partition of the unit sphere S d ⊂ R d+1 into N regions of equal area and small diameter.. The recursive zonal equal area

(The Elliott-Halberstam conjecture does allow one to take B = 2 in (1.39), and therefore leads to small improve- ments in Huxley’s results, which for r ≥ 2 are weaker than the result

Key words and phrases: higher order difference equation, periodic solution, global attractivity, Riccati difference equation, population model.. Received October 6, 2017,

(iii) In Section 4 we show that under the assumptions of Theorem 2.1(i) there exists a positive bounded initial condition u o , for which the solution of the par- abolic problem

In recent work [23], authors proved local-in-time existence and uniqueness of strong solutions in H s for real s > n/2 + 1 for the ideal Boussinesq equations in R n , n = 2, 3

(Furthermore, a bound on the number of elementary matrices can be found that depends only on n, and is universal for all fields.) In the case of fields, this can easily be

If the inequality defined by (1.1) holds for all nonnegative functions f, then {S n , n ≥ 1} is a sub- martingale with respect to the natural choice of σ-algebras.. A martingale

The purpose of this paper is to show that the well known Murnaghan-Nakayama formula for irreducible characters of S n can be derived from the seminormal representations by a