Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - BPA bisimilarity is EXPTIME-hard


Stefan Kiefer. BPA bisimilarity is EXPTIME-hard. Information Processing Letters (IPL), 113(4):101–106, 2013.


Given a basic process algebra (BPA) and two stack symbols, the BPA bisimilarity problem asks whether the two stack symbols are bisimilar. We show that this problem is EXPTIME-hard.

Suggested BibTeX entry:

    author = {Stefan Kiefer},
    journal = {Information Processing Letters (IPL)},
    number = {4},
    pages = {101--106},
    title = {{BPA} bisimilarity is {EXPTIME}-hard},
    volume = {113},
    year = {2013}

PDF (160 kB)
See ...