Characterization and computation of ancestors in reaction systems
| Autor: | Paolo Milazzo, Anna Bernasconi, Roberta Gori, Roberto Barbuti |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
Ancestor computation Causality relations Computational complexity Reaction systems Computational complexity theory True quantified Boolean formula Computer science 0102 computer and information sciences 02 engineering and technology 01 natural sciences Constructive Theoretical Computer Science Set (abstract data type) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Production (computer science) Geometry and Topology Computational problem Time complexity Software Ancestor |
| Zdroj: | Soft Computing. 25:1683-1698 |
| ISSN: | 1433-7479 1432-7643 |
| DOI: | 10.1007/s00500-020-05300-0 |
| Popis: | In reaction systems, preimages and nth ancestors are sets of reactants leading to the production of a target set of products in either 1 or n steps, respectively. Many computational problems on preimages and ancestors, such as finding all minimum-cardinality nth ancestors, computing their size or counting them, are intractable. In this paper, we characterize all nth ancestors using a Boolean formula that can be computed in polynomial time. Once simplified, this formula can be exploited to easily solve all preimage and ancestor problems. This allows us to directly relate the difficulty of ancestor problems to the cost of the simplification so that new insights into computational complexity investigations can be achieved. In particular, we focus on two problems: (i) deciding whether a preimage/nth ancestor exists and (ii) finding a preimage/nth ancestor of minimal size. Our approach is constructive, it aims at finding classes of reactions systems for which the ancestor problems can be solved in polynomial time, in exact or approximate way. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink