| 作成者 |
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
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.続きを見る
|
Mendeley出力
doi-tr-134