Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete
CC BY
Lưu vào:
Tác giả chính: | , |
---|---|
Định dạng: | Sách |
Ngôn ngữ: | English |
Nhà xuất bản: |
Springer
2023
|
Chủ đề: | |
Truy cập trực tuyến: | https://link.springer.com/article/10.1007/s00224-023-10121-3 https://dlib.phenikaa-uni.edu.vn/handle/PNK/8362 |
Từ khóa: |
Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
|
id |
oai:localhost:PNK-8362 |
---|---|
record_format |
dspace |
spelling |
oai:localhost:PNK-83622023-04-27T08:03:46Z Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete Stefan, Göller Mathieu, Hilaire PTA PSPACENEXP CC BY Parametric timed automata (PTA) have been introduced by Alur, Henzinger, and Vardi as an extension of timed automata in which clocks can be compared against parameters. The reachability problem asks for the existence of an assignment of the parameters to the non-negative integers such that reachability holds in the underlying timed automaton. The reachability problem for PTA is long known to be undecidable, already over three parametric clocks. A few years ago, Bundala and Ouaknine proved that for PTA over two parametric clocks and one parameter the reachability problem is decidable and also showed a lower bound for the complexity class PSPACENEXP. 2023-04-27T08:03:45Z 2023-04-27T08:03:45Z 2023 Book https://link.springer.com/article/10.1007/s00224-023-10121-3 https://dlib.phenikaa-uni.edu.vn/handle/PNK/8362 en application/pdf Springer |
institution |
Digital Phenikaa |
collection |
Digital Phenikaa |
language |
English |
topic |
PTA PSPACENEXP |
spellingShingle |
PTA PSPACENEXP Stefan, Göller Mathieu, Hilaire Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete |
description |
CC BY |
format |
Book |
author |
Stefan, Göller Mathieu, Hilaire |
author_facet |
Stefan, Göller Mathieu, Hilaire |
author_sort |
Stefan, Göller |
title |
Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete |
title_short |
Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete |
title_full |
Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete |
title_fullStr |
Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete |
title_full_unstemmed |
Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete |
title_sort |
reachability in two-parametric timed automata with one parameter is expspace-complete |
publisher |
Springer |
publishDate |
2023 |
url |
https://link.springer.com/article/10.1007/s00224-023-10121-3 https://dlib.phenikaa-uni.edu.vn/handle/PNK/8362 |
_version_ |
1764358631853129728 |
score |
8.891145 |