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 extensions 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