On the complexity of occurrence and convergence problems in reaction systems

详细信息    查看全文

• 作者：Enrico Formenti (1)
  Luca Manzoni (1)
  Antonio E. Porreca (2)
  
  1. University of Nice Sophia Antipolis ; CNRS ; I3S ; UMR 7271 ; 06900 ; Sophia Antipolis ; France
  2. Dipartimento di Informatica ; Sistemistica e Comunicazione ; Universit脿 degli Studi di Milano-Bicocca ; Viale Sarca 336/14 ; 20126 ; Milan ; Italy
  
• 关键词：Reaction systems ; Computational complexity ; Discrete dynamical systems
• 刊名：Natural Computing
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：14
• 期：1
• 页码：185-191
• 全文大小：552 KB
• 参考文献：1. Ehrenfeucht A, Rozenberg G (2007) Reaction systems. Fundamenta Informaticae 75:263鈥?80. http://iospress.metapress.com/content/b86t11hryvwq69l0/
  2. Ehrenfeucht A, Rozenberg G (2009) Introducing time in reaction systems. Theor Comput Sci 410(4):310鈥?22. doi:10.1016/j.tcs.2008.09.043
  3. Manzoni L, Porreca AE (2013) Reaction systems made simple: a normal form and a classification theorem. In: Mauri G, Dennunzio A, Manzoni L, Porreca AE (eds) Unconventional computation and natural computation, 12th international conference, UCNC 2013, Lecture Notes in Computer Science, vol 7956, Springer, New York, pp 150鈥?61. doi:10.1007/978-3-642-39074-6_15
  4. Manzoni L, Po莽as D, Porreca AE (2014) Simple reaction systems and their classification. Int J Found Comput Sci 18(6):1197
  5. Papadimitriou CH (1993) Computational complexity. Addison-Wesley, Reading
  6. Salomaa A (2013a) Functional constructions between reaction systems and propositional logic. Int J Found Comput Sci 24(1):147鈥?59. doi:10.1142/S0129054113500044
  7. Salomaa A (2013b) Minimal and almost minimal reaction systems. Nat Comput 12(3):369鈥?76. doi:10.1007/s11047-013-9372-y .
  8. Sutner K (1995) On the computational complexity of finite cellular automata. J Comput Syst Sci 50(1):87鈥?7. doi:10.1006/jcss.1995.1009
  
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation
  Evolutionary Biology
  Processor Architectures
  Artificial Intelligence and Robotics
  Complexity
  
• 出版者：Springer Netherlands
• ISSN：1572-9796

文摘

Reaction systems are a model of computation inspired by biochemical reactions introduced by Ehrenfeucht and Rozenberg. Two problems related to the dynamics (the evolution of the state with respect to time) of reaction systems, namely, the occurrence and the convergence problems, were recently investigated by Salomaa. In this paper, we prove that both problems are PSPACE-complete when the numerical parameter of the problems (i.e. the time step when a specified element must appear) is given as input. Moreover, they remain PSPACE-complete even for minimal reaction systems.