2014年
Unsafe order-2 tree languages are context-sensitive
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
- ,
- ,
- 巻
- 8412
- 号
- 開始ページ
- 149
- 終了ページ
- 163
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.1007/978-3-642-54830-7_10
- 出版者・発行元
- Springer Verlag
Higher-order grammars have been extensively studied in 1980's and interests in them have revived recently in the context of higher-order model checking and program verification, where higherorder grammars are used as models of higher-order functional programs. A lot of theoretical questions remain open, however, for unsafe higherorder grammars (grammars without the so-called safety condition). In this paper, we show that any tree languages generated by order-2 unsafe grammars are context-sensitive. This also implies that any unsafe order-3 word languages are context-sensitive. The proof involves novel technique based on typed lambda-calculus, such as type-based grammar transformation. © 2014 Springer-Verlag.
- ID情報
-
- DOI : 10.1007/978-3-642-54830-7_10
- ISSN : 1611-3349
- ISSN : 0302-9743
- SCOPUS ID : 84900553053