Dyck-based characterizations of Indexed Languages

Autor:	Fratani, Severine, Voundy, El Makki
Rok vydání:	2014
Předmět:	Computer Science - Formal Languages and Automata Theory
Druh dokumentu:	Working Paper
Popis:	Indexed languages are a generalization of context-free languages and form a proper subset of context-sensitive languages. We propose to generalize to indexed languages several well known characterizations of context-free languages: namely, the characterization by rational transductions defined by Nivat, the Chomsky-Sch\"utzenberger theorem, and the logical characterization proved by Lautemann et al. Comment: The general approach can be improved and some statements are inaccurate
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1409.6112 Zobrazit plný text záznamu View this record from Arxiv