Designing and computing bounds for non-deterministic state machines

Abstract

Normally non-deterministic state machines can be transformed into deterministic FSMs, but this does not work if we allow output on non-deterministic state transitions. However, it can be done by executing the non-deterministic alternatives in parallel keeping the conflicting outputs in a multiplex. We have developed a theoretical mechanism for executing non-deterministic state machines by cloning machines that represent different computational outcomes for future inputs for exactly this purpose