On Nonlinear Prices in Timed Automata

Autor: Devendra Bhave, Shankara Narayanan Krishna, Ashutosh Trivedi

Publikováno v: Electronic Proceedings in Theoretical Computer Science, Vol 232, Iss Proc. V2CPS-16, Pp 65-78 (2016)

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

Externí odkaz: https://doaj.org/article/3484e485e54d4a93839e4a91de61c087

Improved Undecidability Results for Reachability Games on Recursive Timed Automata

Autor: Shankara Narayanan Krishna, Lakshmi Manasa, Ashutosh Trivedi

Publikováno v: Electronic Proceedings in Theoretical Computer Science, Vol 161, Iss Proc. GandALF 2014, Pp 245-259 (2014)

We study reachability games on recursive timed automata (RTA) that generalize Alur-Dill timed automata with recursive procedure invocation mechanism similar to recursive state machines. It is known that deciding the winner in reachability games on RT

Externí odkaz: https://doaj.org/article/0fb220ebd8514e82a0bffc22509a89bb

From Non-Punctuality to Non-Adjacency: A Quest for Decidability of Timed Temporal Logics with Quantifiers

Autor: Shankara Narayanan Krishna, Khushraj Madnani, Manuel Mazo Jr., Paritosh Pandya

Publikováno v: Formal Aspects of Computing.

Metric Temporal Logic (MTL) and Timed Propositional Temporal Logic (TPTL) are prominent real-time extensions of Linear Temporal Logic (LTL). In general, the satisfiability checking problem for these extensions is undecidable when both the future (Unt

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::34650ff0266833504a9cee5f70164369
https://doi.org/10.1145/3571749

SD-Regular Transducer Expressions for Aperiodic Transformations

Autor: Shankara Narayanan Krishna, Luc Dartois, Paul Gastin

Publikováno v: 36th Annual Symposium on Logic in Computer Science (LICS'2021)
36th Annual Symposium on Logic in Computer Science (LICS'2021), Jun 2021, Rome, Italy. ⟨10.1109/LICS52264.2021.9470738⟩
LICS

FO transductions, aperiodic deterministic two-way transducers, as well as aperiodic streaming string transducers are all equivalent models for first order definable functions. In this paper, we solve the long standing open problem of expressions capt

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9bc470d3e36a2b05bb8cb0a08fa516c0
https://hal.science/hal-03283013

The Decidability of Verification under PS 2.0

Autor: Mohamed Faouzi Atig, Parosh Aziz Abdulla, Shankara Narayanan Krishna, Adwait Godbole, Viktor Vafeiadis

Publikováno v: Programming Languages and Systems ISBN: 9783030720186
ESOP
Programming Languages and Systems
Lecture Notes in Computer Science

We consider the reachability problem for finite-state multi-threaded programs under the promising semantics () of Lee et al., which captures most common program transformations. Since reachability is already known to be undecidable in the fragment of

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c13f491085b53a9c856ae2e19bd47039
https://doi.org/10.1007/978-3-030-72019-3_1