An undecidable problem for timed automata

DOI10.1023/A:1008319830371MaRDI QIDQ1300103zbMATH OpenOpenAlexFDO

Authors Anuj Puri

Publication date 2 November 2000

Published in Discrete Event Dynamic Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1008319830371

zbMATH Keywords

counter machineshybrid systemsreachabilitytimed automataundecidability

Mathematics Subject Classification ID

Attainable sets, reachability (93B03) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30) Discrete event control/observation systems (93C65)

Review text

The author investigates the reachability problem for timed automata. He proves that the reachability problem for timed automata in which the coefficients of the guards are from the set \(\{1,\sqrt 2\}\) is undecidable. He introduces counter machines as the vehicle for proving the undecidability result and reduces timed automata with real-valued coefficients into counter machines. Further, the author shows that the parameter synthesis problem for timed automata even in the case of a single parameter is undecidable and he discusses some computational issues for hybrid systems and continuous systems.

Recommendations

• scientific article; zbMATH DE number 1444359
• Undecidability of Universality for Timed Automata with Minimal Resources
• Undecidable Problems About Timed Automata
• Robust parametric reachability for timed automata
• On reachability for hybrid automata over bounded time

Cited in

(7)

• Time-Bounded Reachability Problem for Recursive Timed Automata is Undecidable
• On reachability for hybrid automata over bounded time
• Undecidability over Continuous Time
• scientific article; zbMATH DE number 1444359 (Why is no real title available?)
• Reachability in timed counter systems
• Tools and Algorithms for the Construction and Analysis of Systems
• Temporal logics with incommensurable distances are undecidable

This page was built for publication: An undecidable problem for timed automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1300103)