Computer Science Department, North Carolina State University, 900 Main Campus Drive, Venture III Building, Room 184, Campus Box 8207, Raleigh, NC 27695, USA
Abstract:
We show that checking weak bisimulation equivalence of two context-free processes (also called BPA-processes) is EXPTIME-hard, even under the condition that the processes are normed. Furthermore, checking weak regularity (finiteness up to weak bisimilarity) for context-free processes is EXPTIME-hard as well. Adding a finite control of the minimal non-trivial size of 2 to the BPA process already makes weak bisimilarity undecidable.