Complexity Results on Register Pushdown Automata

Autor:	Senda, Ryoma, Takata, Yoshiaki, Seki, Hiroyuki
Rok vydání:	2019
Předmět:	Computer Science - Formal Languages and Automata Theory Computer Science - Computational Complexity
Druh dokumentu:	Working Paper
Popis:	Register pushdown automata (RPDA) is an extension of classical pushdown automata to handle data values in a restricted way. RPDA attracts attention as a model of a query language for structured documents with data values. The membership and emptiness problems for RPDA are known to be EXPTIME-complete. This paper shows the membership problem becomes PSPACE-complete and NP-complete for nondecreasing and growing RPDA, respectively, while the emptiness problem remains EXPTIME-complete for these subclasses. Comment: Proceedings of the Third Workshop on Software Foundations for Data Interoperability (SFDI2019+), October 28, 2019, Fukuoka, Japan
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1910.10357 Zobrazit plný text záznamu View this record from Arxiv