Article ID Journal Published Year Pages File Type
6875445 Theoretical Computer Science 2018 14 Pages PDF
Abstract
We show that trace inclusion between a OCN and a deterministic OCN is NL-complete, even with arbitrary binary-encoded initial counter-values as part of the input. Secondly, we show that the trace universality problem of nondeterministic OCN, which is equivalent to checking trace inclusion between a finite system and a OCN-process, is Ackermann-complete.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,