TY - GEN
T1 - On word and frontier languages of unsafe higher-order grammars
AU - Asada, Kazuyuki
AU - Kobayashi, Naoki
N1 - Publisher Copyright:
© Kazuyuki Asada and Naoki Kobayashi.
PY - 2016/8/1
Y1 - 2016/8/1
N2 - Higher-order grammars are an extension of regular and context-free grammars, where nonterminals may take parameters. They have been extensively studied in 1980's, and restudied recently in the context of model checking and program verification. We show that the class of unsafe order-(n+1) word languages coincides with the class of frontier languages of unsafe order-n tree languages. We use intersection types for transforming an order-(n+1) word grammar to a corresponding order-n tree grammar. The result has been proved for safe languages by Damm in 1982, but it has been open for unsafe languages, to our knowledge. Various known results on higher-order grammars can be obtained as almost immediate corollaries of our result.
AB - Higher-order grammars are an extension of regular and context-free grammars, where nonterminals may take parameters. They have been extensively studied in 1980's, and restudied recently in the context of model checking and program verification. We show that the class of unsafe order-(n+1) word languages coincides with the class of frontier languages of unsafe order-n tree languages. We use intersection types for transforming an order-(n+1) word grammar to a corresponding order-n tree grammar. The result has been proved for safe languages by Damm in 1982, but it has been open for unsafe languages, to our knowledge. Various known results on higher-order grammars can be obtained as almost immediate corollaries of our result.
KW - Higher-order grammars
KW - Intersection types
UR - http://www.scopus.com/inward/record.url?scp=85012892598&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85012892598&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2016.111
DO - 10.4230/LIPIcs.ICALP.2016.111
M3 - Conference contribution
AN - SCOPUS:85012892598
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
A2 - Rabani, Yuval
A2 - Chatzigiannakis, Ioannis
A2 - Sangiorgi, Davide
A2 - Mitzenmacher, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
Y2 - 12 July 2016 through 15 July 2016
ER -