The Label Splitting Problem

Applications of Region Theory 2011.

社会科学（总论）;计算机科学

J. Carmona

Others  :  http://ceur-ws.org/Vol-725/paper02.pdf
PID  :  41565

来源: CEUR

【 摘 要 】

The theory of regions was introduced by Ehrenfeucht and Rozenberg in the early nineties to explain how to derive (synthesize) an event-based model from an automaton. To be applicable, the theory relies on stringent conditions on the input automaton. Although some relaxation on these restrictions has been done in the last decade, in general not every automaton can be synthesized while preserving its behavior. A crucial step for a non-synthesizable automaton is to transform it in order to satisfy the synthesis conditions. This paper revisits label splitting, a technique to satisfy the synthesis conditions through renaming of problematic labels. For the first time, the problem is formally characterized and its optimality addressed.