• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Functional Constructions Between Reaction Systems and Propositional Logic

Arto Salomaa, Functional Constructions Between Reaction Systems and Propositional Logic. International Journal of Foundations of Computer Science 24, 147–159, 2013.

http://dx.doi.org/10.1142/S0129054113500044

Abstract:

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.

BibTeX entry:

@ARTICLE{jSalomaa_Arto13a,
  title = {Functional Constructions Between Reaction Systems and Propositional Logic},
  author = {Salomaa, Arto},
  journal = {International Journal of Foundations of Computer Science},
  volume = {24},
  pages = {147–159},
  year = {2013},
  keywords = {reaction system, truth function, total function, NP-completeness},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication