The Emptiness Problem for Lexical-Functional Grammars is Undecidable

スポンサーリンク

概要

• 論文の詳細を見る

• J. Bresnan and R.M. Kaplan introduced lexical-functional grammars (LFGs, for short) as a new formalism for human language syntax. It is important to show formal properties of this kind of grammars in order to characterize the formal complexity of human languages. In this paper, we will show that the emptiness problem for LFGs is undecidable.

• 社団法人電子情報通信学会の論文
• 1994-05-25

著者

• Nishino Tetsuro

  School Of Information Science Japan Advanced Institute Of Science And Technology

関連論文

• On the Negation-Limited Circuit Complexity of Clique Functions
• The Emptiness Problem for Lexical-Functional Grammars is Undecidable
• A Simulation Result for Simultaneously Bounded AuxPDAs
• On the Number of Negations Needed to Compute Parity Functions

スポンサーリンク