Cover Image

Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete

CC BY

Saved in:
Bibliographic Details
Main Authors: Stefan, Göller, Mathieu, Hilaire
Format: Book
Language:English
Published: Springer 2023
Subjects:
PTA
PSPACENEXP
Online Access:https://link.springer.com/article/10.1007/s00224-023-10121-3
https://dlib.phenikaa-uni.edu.vn/handle/PNK/8362
Tags: Add Tag
No Tags, Be the first to tag this record!
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

Similar Items