On word and frontier languages of unsafe higher-order grammars

DOI10.4230/LIPICS.ICALP.2016.111MaRDI QIDQ4598252zbMATH OpenOpenAlexFDO

Authors Kazuyuki Asada, Naoki Kobayashi

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1604.01595

zbMATH Keywords

intersection typeshigher-order grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Abstract: Higher-order grammars are extensions of regular and context-free grammars, where non-terminals 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.

Recommendations

• Unsafe order-2 tree languages are context-sensitive
• Foundations of Software Science and Computational Structures
• Automata, Languages and Programming
• Pumping Lemma for Higher-order Languages
• Second-Order Simple Grammars

Cited in

(8)

• Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered
• Automata, Languages and Programming
• Unsafe order-2 tree languages are context-sensitive
• Safety in grammatical protection systems
• On higher-order reachability games vs may reachability
• Foundations of Software Science and Computational Structures
• scientific article; zbMATH DE number 7526052 (Why is no real title available?)
• Inclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable

This page was built for publication: On word and frontier languages of unsafe higher-order grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598252)