Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2018.39
URN: urn:nbn:de:0030-drops-95779
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9577/
Krishna, Shankara Narayanan ; Madnani, Khushraj ; Pandya, Paritosh K.
Logics Meet 1-Clock Alternating Timed Automata
| pdf-format: |
|
Abstract
This paper investigates a decidable and highly expressive real time logic QkMSO which is obtained by extending MSO[<] with guarded quantification using block of less than k metric quantifiers. The resulting logic is shown to be expressively equivalent to 1-clock ATA where loops are without clock resets, as well as, RatMTL, a powerful extension of MTL[U_I] with regular expressions. We also establish 4-variable property for QkMSO and characterize the expressive power of its 2-variable fragment. Thus, the paper presents progress towards expressively complete logics for 1-clock ATA.
BibTeX - Entry
@InProceedings{krishna_et_al:LIPIcs:2018:9577,
author = {Shankara Narayanan Krishna and Khushraj Madnani and Paritosh K. Pandya},
title = {{Logics Meet 1-Clock Alternating Timed Automata}},
booktitle = {29th International Conference on Concurrency Theory (CONCUR 2018)},
pages = {39:1--39:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-087-3},
ISSN = {1868-8969},
year = {2018},
volume = {118},
editor = {Sven Schewe and Lijun Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9577},
URN = {urn:nbn:de:0030-drops-95779},
doi = {10.4230/LIPIcs.CONCUR.2018.39},
annote = {Keywords: Metric Temporal Logic, Alternating Timed Automata, MSO, Regular Expressions, Expressive Completeness}
}
| Keywords: | Metric Temporal Logic, Alternating Timed Automata, MSO, Regular Expressions, Expressive Completeness | |
| Seminar: | 29th International Conference on Concurrency Theory (CONCUR 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 31.08.2018 |
