A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Functional constructions between reaction systems and propositional logic




TekijätArto Salomaa

KustantajaWORLD SCIENTIFIC PUBL CO PTE LTD

Julkaisuvuosi2013

JournalInternational Journal of Foundations of Computer Science

Tietokannassa oleva lehden nimiINTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

Lehden akronyymiINT J FOUND COMPUT S

Numero sarjassa1

Vuosikerta24

Numero1

Aloitussivu147

Lopetussivu159

Sivujen määrä13

ISSN0129-0541

DOIhttps://doi.org/10.1142/S0129054113500044


Tiivistelmä

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.




Last updated on 2024-26-11 at 19:42