论文标题
布尔国家分离的复杂性（技术报告）
The Complexity of Boolean State Separation (Technical Report)
论文作者
论文摘要
对于布尔类型的净$τ$，当$ a $的过渡系统$ a $当时可以合成为$τ$ -NET $ n $，并且仅当$ a $的不同状态与$ n $的不同标记相对应，而$ n $则可以防止在$ a $中没有相关过渡的情况下过渡点火。以前的属性称为$τ$ -STATE分离属性（$τ$ -SSP），而后者 - $τ$ -EVENT/State Exparation属性（$τ$ -essp）。 $ a $可嵌入到$τ$ -NET $ n $的可触及度图中，并且仅当$ a $具有$τ$ -SSP。本文介绍了所有布尔Petri Net类型的\ textsc {$τ$ -SSP}的计算复杂性的完整表征。
For a Boolean type of nets $τ$, a transition system $A$ is synthesizeable into a $τ$-net $N$ if and only if distinct states of $A$ correspond to distinct markings of $N$, and $N$ prevents a transition firing if there is no related transition in $A$. The former property is called $τ$-state separation property ($τ$-SSP) while the latter -- $τ$-event/state separation property ($τ$-ESSP). $A$ is embeddable into the reachability graph of a $τ$-net $N$ if and only if $A$ has the $τ$-SSP. This paper presents a complete characterization of the computational complexity of \textsc{$τ$-SSP} for all Boolean Petri net types.
