A1 Refereed original research article in a scientific journal
Functional constructions between reaction systems and propositional logic
Authors: Arto Salomaa
Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD
Publication year: 2013
Journal: International Journal of Foundations of Computer Science
Journal name in source: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Journal acronym: INT J FOUND COMPUT S
Number in series: 1
Volume: 24
Issue: 1
First page : 147
Last page: 159
Number of pages: 13
ISSN: 0129-0541
DOI: https://doi.org/10.1142/S0129054113500044
We investigate formal properties, mainly issues connected with propositional logic, of reaction systems introduced by Ehrenfeucht and Rozenberg. We are concerned only with the most simple variant of the systems. Basic properties of propositional formulas are expressed in terms of reaction systems. This leads to NP-completeness (resp. co-NP-completeness) of many problems concerning reaction systems. Among such problems are: (i) deciding whether the function defined by the system is total, (ii) determining the inverse of the function, (iii) deciding whether state sequences always end with a loop. Propositional formulas with monotonic truth-functions yield a particularly simple representation in terms of reaction systems.