Solution to the predecessors and Gardens-of-Eden problems for synchronous systems over directed graphs

摘要

In this work, we give a solution to the predecessors problems for synchronous systems over directed graphs, so extending the results given for systems over undirected graphs. In this same sense, we provide a characterization to have at least one predecessor for any given state and, consequently, a characterization of the Garden-of-Eden states. Furthermore, we solve the unique predecessor problem, the coexistence of predecessors problem and the number of predecessors problem, providing the best bounds for such a number and for the number of Garden-of-Eden states.