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 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.
Titolo: | Event-Clock Nested Automata |
Autori: | PERON, ADRIANO (Corresponding) |
Data di pubblicazione: | 2018 |
Rivista: | |
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 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. |
Handle: | http://hdl.handle.net/11588/727611 |
ISBN: | 9783319773124 |
Appare nelle tipologie: | 4.1 Articoli in Atti di convegno |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
Bozzelli2018_Chapter_Event-ClockNestedAutomata.pdf | Articolo principale | Documento in Post-print | Accesso privato/ristretto | Administrator Richiedi una copia |