Timed Pushdown Automata Revisited

DOI10.1109/LICS.2015.73zbMATH Open1401.68157arXiv1503.02422OpenAlexW1524026935WikidataQ130981265 ScholiaQ130981265MaRDI QIDQ4635851

Author name not available (Why is that?)

Publication date: 23 April 2018

Published in: (Search for Journal in Brave)

Abstract: This paper contains two results on timed extensions of pushdown automata (PDA). As our first result we prove that the model of dense-timed PDA of Abdulla et al. collapses: it is expressively equivalent to dense-timed PDA with timeless stack. Motivated by this result, we advocate the framework of first-order definable PDA, a specialization of PDA in sets with atoms, as the right setting to define and investigate timed extensions of PDA. The general model obtained in this way is Turing complete. As our second result we prove NEXPTIME upper complexity bound for the non-emptiness problem for an expressive subclass. As a byproduct, we obtain a tight EXPTIME complexity bound for a more restrictive subclass of PDA with timeless stack, thus subsuming the complexity bound known for dense-timed PDA.

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

Mathematics Subject Classification ID

No records found.

This page was built for publication: Timed Pushdown Automata Revisited

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