We study the complexity of the following three relational problems: let-be a binary relation on finite state processes; let p sub 0 be a fixed finite state process; and let pai be a nontrivial predicate on finite state processes such that x and y are weakly bisimilar implies pai(x)=pai(y). (i) P sub 1: Determine for processes p and q, if p-q; (ii) P sub 2: Determine for process p, if p-p sub 0; and (iii) P sub 3: Determine for process p, if pai(p)=true. We study the complexties of these problems, when processes are represented y sequential transition systems and by parallel composition of transition systems. A number of results are obtained for both representations.
展开▼
机译：我们研究以下三个关系问题的复杂性：设有限状态过程的二元关系；令p sub 0为固定的有限状态过程；并令pai为有限状态过程的非平凡谓词，以使x和y呈弱双相似性，意味着pai（x）= pai（y）。 （i）P子1：如果p-q，则确定过程p和q； （ii）P sub 2：如果p-p sub 0，则确定过程p； （iii）P sub 3：如果pai（p）= true，则确定过程p。当过程由顺序转换系统和转换系统的并行组成表示时，我们研究了这些问题的复杂性。两种表示形式都获得了许多结果。
展开▼
