
A simple algorithm for solving the coverability problem for monotonic counter systems
A. V. Klimov^{} ^{} M. V. Keldysh Institute for Applied Mathematics, Russian Academy of Sciences, Moscow
Abstract:
An algorithm for solving the coverability problem for monotonic counter systems is presented. The solvability of this problem is wellknown, but the algorithm is interesting due to its simplicity. The algorithm has emerged as a simplification of a certain procedure of a supercompiler application (a program specializer based on V.F. Turchin's supercompilation) to a program encoding a monotonic counter system along with initial and target sets of states and from the proof that under some conditions the procedure terminates and solves the coverability problem.
Keywords:
wellstructured transition systems, counter systems, reachability, coverability, supercompilation.
Full text:
PDF file (424 kB)
References:
PDF file
HTML file
UDC:
519.681.3 Received: 17.10.2011
Citation:
A. V. Klimov, “A simple algorithm for solving the coverability problem for monotonic counter systems”, Model. Anal. Inform. Sist., 18:4 (2011), 106–117
Citation in format AMSBIB
\Bibitem{Kli11}
\by A.~V.~Klimov
\paper A simple algorithm for solving the coverability problem for monotonic counter systems
\jour Model. Anal. Inform. Sist.
\yr 2011
\vol 18
\issue 4
\pages 106117
\mathnet{http://mi.mathnet.ru/mais202}
Linking options:
http://mi.mathnet.ru/eng/mais202 http://mi.mathnet.ru/eng/mais/v18/i4/p106
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles

Number of views: 
This page:  174  Full text:  62  References:  18 
