<テクニカルレポート>
On the Complexity of Languages Definable by Hereditary Elementary Formal Systems

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 An elementary formal system (EFS) is a logical system that generates a language. In this paper, we consider a subclass of EFS, called hereditary EFS (HEFS). First, we compare HEFS with the following e...xtensions of pattern languages: multipattern languages, languages defined by pattern grammars, and non-synchronized pattern languages. Particularly, we show that a subclass of HEFS called simple EFS (SEFS) precisely generates non-synchronized pattern languages, and the subclass of SEFS with only one predicate symbol precisely generates the languages defined by pattern grammars. Next, we analyze the complexity of the languages definable by HEFS. We show that HEFS exactly defines the complexity class P, the class of languages accepted by deterministic Turing machines in polynomial time. This seems to be the first result to characterize the class P by grammars, while various characterization results by automata, logic, recursive functions, algebraic systems, lambda calculus are shown in literatures. We also show that a subclass of HEFS, called linear HEFS, exactly defines NSPACE(log η). Finally, we consider the membership problem for HEFS, that is, the problem of, given a string ω and an HEFS Γ, determining whether Г generates ω. We prove that the membership problem is EXPTIME-complete for HEFS, and NP-complete for SEFS.続きを見る

本文情報を非表示

doi-tr-134 pdf 825 KB 76  

詳細

レコードID
査読有無
関連情報
タイプ
登録日 2009.04.22
更新日 2017.01.20