Equivalence-Checking with One-Counter Automata: A Generic Method for Proving Lower Bounds
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F02%3A00005571" target="_blank" >RIV/00216224:14330/02:00005571 - isvavai.cz</a>
Alternative codes found
RIV/61989100:27240/02:00006674
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Equivalence-Checking with One-Counter Automata: A Generic Method for Proving Lower Bounds
Original language description
We present a general method for proving DP-hardness of equivalence-checking problems on one-counter automata. For this we show a reduction of the SAT-UNSAT problem to the truth problem for a fragment of (Presburger) arithmetic. The fragment contains onlyspecial formulas with one free variable, and is particularly apt for transforming to simulation-like equivalences on one-counter automata. In this way we show that the membership problem for any relation subsuming bisimilarity and subsumed by simulationpreorder is DP-hard (even) for one-counter nets (where the counter cannot be tested for zero). We also show DP-hardness for deciding simulation between one-counter automata and finite-state systems (in both directions).
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F00%2F0400" target="_blank" >GA201/00/0400: Infinite state concurrent systems - models and verification</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2002
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 5th International Conference on Foundations of Software Science and Computation Structures (FOSSACS 2002)
ISBN
3-540-43366-X
ISSN
—
e-ISSN
—
Number of pages
15
Pages from-to
172
Publisher name
Springer
Place of publication
Berlin, Heidelberg, New York
Event location
Grenoble, France, April 8-12, 2002
Event date
Jan 1, 2002
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—