{'fraction_non_alphanumeric': 0.03219178082191781, 'fraction_numerical': 0.005479452054794521, 'mean_word_length': 4.492481203007519, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Finding an Optimal Label-Splitting to Make a Transition System Petri Net Implementable: a Complete Complexity Characterization

Petri net synthesis is the task of finding a Petri net N for a given transition system (TS) A that implements A, i.e., N is an (exact net) realization, a language-simulation or an embedding of A according to N ’s degree of accuracy. Regardless of the sought implementation, there is not always a solution. Label-splitting converts a non-implementable TS A into an implementable one by giving edges with the same label now different labels. Since increasing the number of labels increases the complexity of the net synthesized, it is desired to keep the number of split labels small. This means that label-splitting can be considered as decision problem that asks for a given TS A and natural number κ whether there is an implementable TS B with at most κ labels that is derived from A by splitting labels. Recently, Schlachter and Wimmel (2020) [18] showed that this problem is NP-complete if an embedding is sought. In this paper, we show that this remains true if A is 2-bounded, i.e., every state has at most two incoming and two outgoing edges, and that this bound is tight. Schlachter and Wimmel also alleged that label-splitting aiming at exact realization is NP-complete. In this paper, we prove this conjecture and show that label-splitting aiming at language-simulation or realization is NP-complete even if A is 1-bounded.