The Complexity of Synthesizing nop-Equipped Boolean Nets from g-Bounded\n Inputs (Technical Report)

2019/11/01 by Ronny Tredup, Tredup, Ronny
Biochemistry, Genetics and Molecular Biology · Computer Science · #Computational Complexity (cs.CC) #DNA and Biological Computing #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Petri Nets in System Modeling

paper · pdf · doi:10.48550/arxiv.1911.05834

openalex publication_date 2019/11/01 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

Boolean Petri nets equipped with nop allow places and transitions to be\nindependent by being related by nop. We characterize for any fixed natural\nnumber g the computational complexity of synthesizing nop-equipped Boolean\nPetri nets from labeled directed graphs whose states have at most g incoming\nand at most g outgoing arcs.\n

Related

• Towards Completely Characterizing the Complexity of Boolean Nets\n Synthesis
• The Complexity of Boolean State Separation (Technical Report)
• On the Parameterized Complexity of Synthesizing Boolean Petri Nets With Restricted Dependency (Technical Report)
• Hardness Results for the Synthesis of b-bounded Petri Nets (Technical\n Report)
• mpbn: a simple tool for efficient edition and analysis of elementary properties of Boolean networks