Output details
11 - Computer Science and Informatics
University of Edinburgh
Return to search
Output 0 of 0 in the submission
Output title
Decidability of Weak Simulation on One-Counter Nets
Type
E - Conference contribution
Name of conference/published proceedings
Logic in Computer Science (LICS), 2013 28th Annual IEEE/ACM Symposium on
Volume number
-
Issue number
-
First page of article
203
ISSN of proceedings
-
Year of publication
2013
Number of additional authors
2
Additional information
<10> Originality: Solution of two long-standing open problems on semantic preorders.
Significance: Due to the difficulties of handling infinite branching induced by weak internal actions, there are hardly any algorithms for checking weak semantic preorders/equivalences on infinite-state systems. This paper describes a major new technique for computing approximants to weak simulation preorder and shows its decidability on one-counter nets, thus settling a question that has been open for more than 15 years. The result is very surprising, since both finer and coarser preorders are undecidable.
Rigour: The paper (24p with electronic appendices) provides full formal details of all proofs.
Interdisciplinary
-
Cross-referral requested
-
Research group
F - Laboratory for Foundations of Computer Science
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
