On word and frontier languages of unsafe higher-order grammars
From MaRDI portal
Publication:4598252
DOI10.4230/LIPICS.ICALP.2016.111zbMATH Open1388.68157arXiv1604.01595OpenAlexW2964277871MaRDI QIDQ4598252FDOQ4598252
Authors: Kazuyuki Asada, Naoki Kobayashi 
Publication date: 19 December 2017
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.
Full work available at URL: https://arxiv.org/abs/1604.01595
Recommendations
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
- Title not available (Why is that?)
- 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)
