2014/03/20 by Sven Schneider, Schneider, Sven, Uwe Nestmann +1
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL
paper · pdf · doi:10.48550/arxiv.1403.5081
arxiv created 2014/03/21 · arxiv updated 2014/03/24
We present an algorithm which modifies a deterministic pushdown automaton (DPDA) such that (i) the marked language is preserved, (ii) lifelocks are removed, (iii) deadlocks are removed, (iv) all states and edges are accessible, and (v) operational blockfreeness is established (i.e., coaccessibility in the sense that every initial derivation can be continued to a marking configuration). This problem can be trivially solved for deterministic finite automata (DFA) but is not solvable for standard petri net classes. The algorithm is required for an operational extension of the supervisory control problem (SCP) to the situation where the specification in modeled by a DPDA.