Event-clock nested automata

DOI10.1007/978-3-319-77313-1_6MaRDI QIDQ1647682zbMATH OpenOpenAlexFDO

Authors Laura Bozzelli, Aniello Murano, Adriano Peron

Publication date 26 June 2018

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: In this paper we introduce and study Event-Clock Nested Automata (ECNA), a formalism that combines Event Clock Automata (ECA) and Visibly Pushdown Automata (VPA). ECNA allow to express real-time properties over non-regular patterns of recursive programs. We prove that ECNA retain the same closure and decidability properties of ECA and VPA being closed under Boolean operations and having a decidable language-inclusion problem. In particular, we prove that emptiness, universality, and language-inclusion for ECNA are EXPTIME-complete problems. As for the expressiveness, we have that ECNA properly extend any previous attempt in the literature of combining ECA and VPA.

Recommendations

• Event-Clock Visibly Pushdown Automata
• Event clock automata: from theory to practice
• Memory event clocks
• Event-clock automata: a determinizable class of timed automata
• On regions and zones for event-clock automata

Cited in

(9)

• Context-free timed formalisms: robust automata and linear temporal logics
• Event-clock automata: a determinizable class of timed automata
• Simulations for event-clock automata
• On the determinization of event-clock input-driven pushdown automata
• Memory event clocks
• Event-Clock Visibly Pushdown Automata
• scientific article; zbMATH DE number 7447746 (Why is no real title available?)
• Event clock automata: from theory to practice
• scientific article; zbMATH DE number 1390065 (Why is no real title available?)

This page was built for publication: Event-clock nested automata

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