Event-clock nested automata

DOI10.1007/978-3-319-77313-1_6zbMATH Open1504.68096arXiv1711.08314OpenAlexW2962885229MaRDI QIDQ1647682FDOQ1647682

Authors: Laura Bozzelli, Aniello Murano, Adriano Peron 

Publication date: 26 June 2018

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.

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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
• Title not available (Why is that?)
• Event clock automata: from theory to practice
• Title not available (Why is that?)

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)