On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911572319797248 |
|---|---|
| author | Devillers, Raymond Tredup, Ronny |
| author_facet | Devillers, Raymond Tredup, Ronny |
| contents | Synthesis consists in deciding whether a given labeled transition system (TS) $A$ can be implemented by a net $N$ of type $τ$. In case of a negative decision, it may be possible to convert $A$ into an implementable TS $B$ by applying various modification techniques, like relabeling edges that previously had the same label, suppressing edges/states/events, etc. It may however be useful to limit the number of such modifications to stay close to the original problem, or optimize the technique. In this paper, we show that most of the corresponding problems are NP-complete if $τ$ corresponds to the type of flip-flop nets or some flip-flop net derivatives. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_09233 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets Devillers, Raymond Tredup, Ronny Computational Complexity Synthesis consists in deciding whether a given labeled transition system (TS) $A$ can be implemented by a net $N$ of type $τ$. In case of a negative decision, it may be possible to convert $A$ into an implementable TS $B$ by applying various modification techniques, like relabeling edges that previously had the same label, suppressing edges/states/events, etc. It may however be useful to limit the number of such modifications to stay close to the original problem, or optimize the technique. In this paper, we show that most of the corresponding problems are NP-complete if $τ$ corresponds to the type of flip-flop nets or some flip-flop net derivatives. |
| title | On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2203.09233 |