Technical Reports

The report FIMU-RS-96-01

Regularity is Decidable for Normed PA Processes in Polynomial Time

by Antonín Kuèera, This paper is going to be presented at FST&TCS`96 conference, LNCS 1180, Springer-Verlag. February 1996, 17 pages.

FIMU-RS-96-01. Available as Postscript, PDF.

Abstract:

A process X is regular if it is bisimilar to a process X` with finitely many states. We prove that regularity of normed PA processes is decidable and we present a practically usable polynomial-time algorithm. Moreover, if the tested normed PA process X is regular then the process X` can be effectively constructed. It implies decidability of bisimulation equivalence for any pair of processes such that one process is a normed PA process and the other process has finitely many states.