BPA bisimilarity is EXPTIME-hard

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. ► It is shown that BPA bisimilarity is EXPTIME-hard. ► This improves on PSPACE-hardness, which was shown by Srba in 200...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2013-02, Vol.113 (4), p.101-106
Main Author: Kiefer, Stefan
Format: Article
Language:English
Subjects:
Algebra
Basic process algebra
Bisimilarity
Computational complexity
Computer science
Data processing
Mathematical problems
Stacks
Studies
Symbols
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. ► It is shown that BPA bisimilarity is EXPTIME-hard. ► This improves on PSPACE-hardness, which was shown by Srba in 2002. ► The proof is based on EXPTIME-hardness of a reachability game involving succinct counters.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2012.12.004