Shankara Narayanan Krishna

Devendra Bhave, Shankara Narayanan Krishna, Ashutosh Trivedi

Priced timed automata provide a natural model for quantitative analysis of real-time systems and have been successfully applied in various scheduling and planning problems. The optimal reachability problem for linearly-priced timed automata is known to be PSPACE-complete. In this paper we investigate priced timed automata with more general prices and show that in the most general setting the optimal reachability problem is undecidable. We adapt and implement the construction of Audemard, Cimatti, Kornilowicz, and Sebastiani for non-linear priced timed automata using state-of-the-art theorem prover Z3 and present some preliminary results.

Shankara Narayanan Krishna, Khushraj Nanik Madnani, Rupak Majumdar et al.

We investigate the decidability of the ${0,\infty}$ fragment of Timed Propositional Temporal Logic (TPTL). We show that the satisfiability checking of TPTL$^{0,\infty}$ is PSPACE-complete. Moreover, even its 1-variable fragment (1-TPTL$^{0,\infty}$) is strictly more expressive than Metric Interval Temporal Logic (MITL) for which satisfiability checking is EXPSPACE complete. Hence, we have a strictly more expressive logic with computationally easier satisfiability checking. To the best of our knowledge, TPTL$^{0,\infty}$ is the first multi-variable fragment of TPTL for which satisfiability checking is decidable without imposing any bounds/restrictions on the timed words (e.g. bounded variability, bounded time, etc.). The membership in PSPACE is obtained by a reduction to the emptiness checking problem for a new "non-punctual" subclass of Alternating Timed Automata with multiple clocks called Unilateral Very Weak Alternating Timed Automata (VWATA$^{0,\infty}$) which we prove to be in PSPACE. We show this by constructing a simulation equivalent non-deterministic timed automata whose number of clocks is polynomial in the size of the given VWATA$^{0,\infty}$.

Shankara Narayanan Krishna, Aviral Kumar, Fabio Somenzi et al.

A constant-rate multi-mode system is a hybrid system that can switch freely among a finite set of modes, and whose dynamics is specified by a finite number of real-valued variables with mode-dependent constant rates. Alur, Wojtczak, and Trivedi have shown that reachability problems for constant-rate multi-mode systems for open and convex safety sets can be solved in polynomial time. In this paper, we study the reachability problem for non-convex state spaces and show that this problem is in general undecidable. We recover decidability by making certain assumptions about the safety set. We present a new algorithm to solve this problem and compare its performance with the popular sampling based algorithm rapidly-exploring random tree (RRT) as implemented in the Open Motion Planning Library (OMPL).

Shankara Narayanan Krishna, Ganesh Narwane, Ramesh S. et al.

In the literature, the definition of product in a Software Product Line (SPL) is based upon the notion of consistency of the constraints, imposed by variability and traceability relations on the elements of the SPL. In this paper, we contend that consistency does not model the natural semantics of the implementability relation between problem and solution spaces correctly. Therefore, we define when a feature can be {\em derived} from a set of components . Using this, we define a product of the SPL by a <specification, architecture> pair, where all the features in the specification are derived from the components in the architecture. This notion of derivability is formulated in a simple yet expressive, abstract model of a productline with traceability relation. We then define a set of SPL analysis problems and show that these problems can be encoded as Quantified Boolean Formulas. Then, QSAT solvers like QUBE can be used to solve the analysis problems. We illustrate the methodology on a small fragment of a realistic productline.