論文

査読有り
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)
  • Naoki Kobayashi
  • ,
  • Kazuhiro Inaba
  • ,
  • Takeshi Tsukada

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.

リンク情報
DOI
https://doi.org/10.1007/978-3-642-54830-7_10
ID情報
  • DOI : 10.1007/978-3-642-54830-7_10
  • ISSN : 1611-3349
  • ISSN : 0302-9743
  • SCOPUS ID : 84900553053

エクスポート
BibTeX RIS