Towards an Efficient Tree Automata based technique for Timed Systems

DOI10.4230/LIPICS.CONCUR.2017.39zbMATH Open1442.68123arXiv1707.02297OpenAlexW2962796379MaRDI QIDQ5111654FDOQ5111654

Authors: S. Akshay, Paul Gastin, Shankara Narayanan Krishna, Ilias Sarkar 

Publication date: 27 May 2020

Abstract: The focus of this paper is the analysis of real-time systems with recursion, through the development of good theoretical techniques which are implementable. Time is modeled using clock variables, and recursion using stacks. Our technique consists of modeling the behaviours of the timed system as graphs, and interpreting these graphs on tree terms by showing a bound on their tree-width. We then build a tree automaton that accepts exactly those tree terms that describe realizable runs of the timed system. The emptiness of the timed system thus boils down to emptiness of a finite tree automaton that accepts these tree terms. This approach helps us in obtaining an optimal complexity, not just in theory (as done in earlier work), but also in going towards an efficient implementation of our technique. To do this, we make several improvements in the theory and exploit these to build a first prototype tool that can analyze timed systems with recursion.

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

Recommendations

• Analyzing Timed Systems Using Tree Automata
• Analyzing timed systems using tree automata
• Timed tree automata with an application to temporal logic.
• scientific article; zbMATH DE number 1405651
• Synthesizing Clock-Efficient Timed Automata
• Lectures on Concurrency and Petri Nets
• Finite automata on timed \(\omega\)-trees
• Branching-time temporal logic and tree automata
• A new method for transforming timed automata
• On implementable timed automata

zbMATH Keywords

pushdown systemstimed automatatree automatatree-width

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• Formal Methods for the Design of Real-Time Systems
• A theory of timed automata
• Nested Timed Automata
• Dense-Timed Pushdown Automata
• Graph structure and monadic second-order logic. A language-theoretic approach
• Timed Pushdown Automata Revisited
• Recursive timed automata
• MSO Decidability of Multi-Pushdown Systems via Split-Width
• The tree width of auxiliary storage
• Towards an Efficient Tree Automata based technique for Timed Systems
• The Minimal Cost Reachability Problem in Priced Timed Pushdown Systems
• Title not available (Why is that?)
• Analyzing Timed Systems Using Tree Automata

Cited In (7)

• Fast zone-based algorithms for reachability in pushdown timed automata
• Analyzing Timed Systems Using Tree Automata
• Bounded Context Switching for Valence Systems
• Revisiting Underapproximate Reachability for Multipushdown Systems
• Towards an Efficient Tree Automata based technique for Timed Systems
• A model of finite automata on timed omega-trees
• Title not available (Why is that?)

Uses Software

• Uppaal

This page was built for publication: Towards an Efficient Tree Automata based technique for Timed Systems

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