Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875445 | Theoretical Computer Science | 2018 | 14 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Piotr Hofman, Patrick Totzke,