Decidability and complexity results for timed automata and semi-linear hybrid automta (Q4953401)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1444359
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Decidability and complexity results for timed automata and semi-linear hybrid automta |
scientific article; zbMATH DE number 1444359 |
Statements
8 September 2002
0 references
hybrid automata
0 references
reachability
0 references
parallel compositions
0 references
algebraic timed automata
0 references
parametric timed automata
0 references
undecidability
0 references
complexity results
0 references
0.8504244089126587
0 references
0.8346111178398132
0 references
0.8338496088981628
0 references
Decidability and complexity results for timed automata and semi-linear hybrid automta (English)
0 references
The author defines a new class of hybrid automata for which reachability is decidable by taking parallel compositions of simple components. Attempting to generalize, he encounters timed automata with algebraic constants. He shows that reachability is undecidable for these algebraic timed automata by simulating two-counter Minsky machines. Modifying the construction to apply to parametric timed automata, he reproves the undecidability of the emptiness problem, and then distinguishes the dense and discrete-time cases with a new result. He finishes with a table of computability-theoretic complexity results. For the entire collection see [Zbl 0934.00029].
0 references
