On string languages generated by sequential spiking neural P systems based on the number of spikes

详细信息    查看全文

• 作者：Keqin Jiang ; Wenli Chen ; Yuzhou Zhang ; Linqiang Pan
• 关键词：Membrane computing ; Spiking neural P system ; Sequentiality ; Language generator
• 刊名：Natural Computing
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：15
• 期：1
• 页码：87-96
• 全文大小：845 KB
• 参考文献：Chen H, Freund R, Ionescu M, Păun Gh, Pérez-Jiménez MJ (2007) On string languages generated by spikng neural P systems. Fund Inform 75:141–162MathSciNet MATH
  Chen H, Ionescu M, Ishdorj T-O, Păun A, Păun Gh, Pérez-Jiménez MJ (2008) Spiking neural P systems with extended rules: universality and languages. Nat Comput 7(2):147–166CrossRef MathSciNet MATH
  Ibarra OH, Păun A, Rodríguez-Patón A (2009) Sequential SNP systems based on min/max spike number. Theor Comput Sci 410(30–32):2982–2991CrossRef MATH
  Ionescu M, Păun G, Yokomori T (2006) Spiking neural P systems. Fund Inform 71(2–3):279–308MathSciNet MATH
  Ishdorj T-O, Leporati A, Pan L, Zeng X, Zhang X (2010) Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources. Theor Comput Sci 411(25):2345–2358CrossRef MathSciNet MATH
  Leporati A, Mauri G, Zandron C, Păun G, Pérez-Jiménez MJ (2009) Uniform solutions to sat and subset sum by spiking neural P systems. Nat Comput 8(4):681–702CrossRef MathSciNet MATH
  Minsky M (1967) Computation—finite and infinite machines. Prentice Hall, Englewood Cliffs, New JerseyMATH
  Pan L, Păun G, Pérez-Jiménez MJ (2011) Spiking neural P systems with neuron division and budding. Sci China Inform Sci 54(8):1596–1607CrossRef MATH
  Pan L, Zeng X (2011) Small universal spiking neural P systems working in exhaustive mode. IEEE Trans Nanobiosci 10(2):99–105CrossRef MathSciNet
  Păun A, Păun Gh (2007) Small universal spiking neural P systems. BioSystems 90(1):48–60CrossRef
  Păun A, Sidoroff M (2012) Sequentiality induced by spike number in SNP systems: small universal machines. LNCS 7184:333–345
  Păun G, Pérez-Jiménez MJ, Rozenberg G (2006) Spike trains in spiking neural P systems. Int J Found Comput Sci 17(4):975–1002CrossRef MATH
  Păun G, Rozenberg G, Salomaa A (eds) (2010) Handbook of membrane computing. Oxford University Press, Oxford
  Rozenberg G, Salomaa A (eds) (1997) Handbook of formal languages, vol 3. Springer, Berlin
  Song T, Pan L, Păun G (2013) Asynchronous spiking neural P systems with local synchronization. Inform Sci 219:197–207CrossRef MathSciNet MATH
  Wang J, Hoogeboom HJ, Pan L, Păun G, Pérez-Jiménez MJ (2010) Spiking neural P systems with weights. Neural Comput 22(10):2615–2646CrossRef MathSciNet MATH
  Zeng X, Zhang X, Pan L (2009) Homogeneous spiking neural P systems. Fund Inform 97:1–20MathSciNet
  Zhang X, Zeng X, Pan L (2009) On languages generated by asynchronous spiking neural P systems. Theor Comput Sci 410(26):2478–2488CrossRef MathSciNet MATH
  Zhang X, Zeng X, Pan L (2008a) On string languages generated by spiking neural P systems with exhaustive use of rules. Nat Comput 7(4):535–549CrossRef MathSciNet MATH
  Zhang X, Zeng X, Pan L (2008b) Smaller universal spiking neural P systems. Fund Inform 87(1):117–136MathSciNet MATH
  
• 作者单位：Keqin Jiang (1) (2)
  Wenli Chen (2)
  Yuzhou Zhang (2)
  Linqiang Pan (1)
  
  1. Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan, 430074, Hubei, China
  2. School of Computer and Information, Anqing Normal University, Anqing, 246133, Anhui, China
  
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation
  Evolutionary Biology
  Processor Architectures
  Artificial Intelligence and Robotics
  Complexity
  
• 出版者：Springer Netherlands
• ISSN：1572-9796

文摘

Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons communicate by means of spikes. In this work, we consider SN P systems with the following restriction: at each step the active neuron with the maximum (or minimum) number of spikes among the neurons that can spike will fire [if there is a tie for the maximum (or minimum) number of spikes stored in the active neurons, only one of the neurons containing the maximum (or minimum) is chosen non-deterministically]. We investigate the computational power of such sequential SN P systems that are used as language generators. We prove that recursively enumerable languages can be characterized as projections of inverse-morphic images of languages generated by such sequential SN P systems. The relationships of the languages generated by these sequential SN P systems with finite and regular languages are also investigated.