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.

Event-Clock Nested Automata / Bozzelli, Laura; Murano, Aniello; Peron, Adriano. - 10792:(2018), pp. 80-92. (Intervento presentato al convegno 12th International Conference on Language and Automata Theory and Applications, LATA 2018 tenutosi a isr nel 2018) [10.1007/978-3-319-77313-1_6].

Event-Clock Nested Automata

Bozzelli, Laura
;
Murano, Aniello
;
Peron, Adriano
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 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.
2018
9783319773124
Event-Clock Nested Automata / Bozzelli, Laura; Murano, Aniello; Peron, Adriano. - 10792:(2018), pp. 80-92. (Intervento presentato al convegno 12th International Conference on Language and Automata Theory and Applications, LATA 2018 tenutosi a isr nel 2018) [10.1007/978-3-319-77313-1_6].
File in questo prodotto:
File Dimensione Formato  
Bozzelli2018_Chapter_Event-ClockNestedAutomata.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Documento in Post-print
Licenza: Accesso privato/ristretto
Dimensione 345.79 kB
Formato Adobe PDF
345.79 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/727611
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact