Predecessors and Gardens of Eden in sequential dynamical systems over directed graphs

[1]N.L. Ackerman, C.E. Freer, Graph Turing Machines, Proceedings of WoLLIC 2017, LNCS Vol. 10388, 1–13, 2017.AckermanN.L.FreerC.E.Graph Turing MachinesProceedings of WoLLIC 2017, LNCS103881132017Search in Google Scholar

[2]J.A. Aledo, L.G. Diaz, S. Martinez, J.C. Valverde, On the periods of parallel dynamical systems, Complexity 2017 (2017), Article ID 7209762, 6 pages. 10.1155/2017/7209762.AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.On the periods of parallel dynamical systemsComplexity20172017Article ID 7209762610.1155/2017/7209762Open DOISearch in Google Scholar

[3]J.A. Aledo, L.G. Diaz, S. Martinez, J.C. Valverde, On periods and equilibria of sequential dynamical systems, Inf. Sci. 409–410 (2017) 27–34. 10.1016/j.ins.2017.05.002.AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.On periods and equilibria of sequential dynamical systemsInf. Sci.4094102017273410.1016/j.ins.2017.05.002Open DOISearch in Google Scholar

[4]J.A. Aledo, L.G. Diaz, S. Martinez and J.C. Valverde, Maximum number of periodic orbits in parallel dynamical systems, Inf. Sci. 468 (2018) 63–71. 10.1016/j.ins.2018.08.041.AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.Maximum number of periodic orbits in parallel dynamical systemsInf. Sci.4682018637110.1016/j.ins.2018.08.041Open DOISearch in Google Scholar

[5]J.A. Aledo, L.G. Diaz, S. Martinez, J.C. Valverde, Predecessors and Garden-of-Eden configurations in parallel dynamical models, J. Comput. Appl. Math. 348 (2019) 26–33. 10.1016/j.cam.2018.08.015.AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.Predecessors and Garden-of-Eden configurations in parallel dynamical modelsJ. Comput. Appl. Math.3482019263310.1016/j.cam.2018.08.015Open DOISearch in Google Scholar

[6]J.A. Aledo, L.G. Diaz, S. Martinez, J.C. Valverde, Solution to the predecessors and Gardens-of-Eden problems for synchronous systems over directed graphs, Appl. Math. Comput. 370 (2019) 22–28. 10.1016/j.amc.2018.10.077.AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.Solution to the predecessors and Gardens-of-Eden problems for synchronous systems over directed graphsAppl. Math. Comput.3702019222810.1016/j.amc.2018.10.077Open DOISearch in Google Scholar

[7]J.A. Aledo, L.G. Diaz, S. Martinez, J.C. Valverde, Predecessors existence problems and Garden-of-Eden in sequential dynamical systems, Complexity (in press)AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.Predecessors existence problems and Garden-of-Eden in sequential dynamical systemsComplexityin press10.1155/2019/6280960Search in Google Scholar

[8]J.A. Aledo, S. Martinez, F.L. Pelayo, J.C. Valverde, Parallel dynamical systems on maxterm and minterm Boolean functions, Math. Comput. Model. 35 (2012), 666–671. 10.1016/j.mcm.2011.08.040.AledoJ.A.MartinezS.PelayoF.L.ValverdeJ.C.Parallel dynamical systems on maxterm and minterm Boolean functionsMath. Comput. Model.35201266667110.1016/j.mcm.2011.08.040Open DOISearch in Google Scholar

[9]J.A. Aledo, S. Martinez, J.C. Valverde, Parallel dynamical systems over directed dependency graphs, Appl. Math. Comput. 219 (2012), 1114–1119. 10.1016/j.amc.2012.07.018.AledoJ.A.MartinezS.ValverdeJ.C.Parallel dynamical systems over directed dependency graphsAppl. Math. Comput.21920121114111910.1016/j.amc.2012.07.018Open DOISearch in Google Scholar

[10]J.A. Aledo, S. Martinez, J.C. Valverde, Parallel discrete dynamical systems on independent local functions, J. Comput. Appl. Math. 237 (2013), 335–339. 10.1016/j.cam.2012.06.002.AledoJ.A.MartinezS.ValverdeJ.C.Parallel discrete dynamical systems on independent local functionsJ. Comput. Appl. Math.237201333533910.1016/j.cam.2012.06.002Open DOISearch in Google Scholar

[11]J.A. Aledo, S. Martinez, J.C. Valverde, Updating method for the computation of orbits in parallel dynamical systems, Int. J. Comput. Math 90 (9) (2013) 1796-1808. 10.1080/00207160.2013.767894.AledoJ.A.MartinezS.ValverdeJ.C.Updating method for the computation of orbits in parallel dynamical systemsInt. J. Comput. Math90920131796180810.1080/00207160.2013.767894Open DOISearch in Google Scholar

[12]J.A. Aledo, S. Martinez and J.C. Valverde. Parallel dynamical systems over graphs and related topics: a survey, J. Appl. Maths 2015 (2015), Article ID 594294, 14 pages. 10.1155/2015/594294.AledoJ.A.MartinezS.ValverdeJ.C.Parallel dynamical systems over graphs and related topics: a surveyJ. Appl. Maths20152015Article ID 5942941410.1155/2015/594294Open DOISearch in Google Scholar

[13]J.A. Aledo, S. Martinez and J.C. Valverde, Graph dynamical systems with general Boolean states, Appl. Math. Inf. Sci. 9 (2015), 1803–1808. 10.12785/amis/090417.AledoJ.A.MartinezS.ValverdeJ.C.Graph dynamical systems with general Boolean statesAppl. Math. Inf. Sci.920151803180810.12785/amis/090417Open DOISearch in Google Scholar

[14]C. Barrett, H. B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, P.T. Tosic, Gardens of Eden and fixed points in sequential dynamical systems, Discrete Math. Theor. Comput. Sci. Proceedings (2001) 95–110.BarrettC.Hunt IIIH. B.MaratheM.V.RaviS.S.RosenkrantzD.J.StearnsR.E.TosicP.T.Gardens of Eden and fixed points in sequential dynamical systemsDiscrete Math. Theor. Comput. Sci. Proceedings20019511010.46298/dmtcs.2294Search in Google Scholar

[15]C. Barrett, H. B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, Predecessor and permutation existence problems for sequential dynamical systems, Discrete Math. Theor. Comput. Sci. AB(DMCS) 2003 69-80BarrettC.Hunt IIIH. B.MaratheM.V.RaviS.S.RosenkrantzD.J.StearnsR.E.Predecessor and permutation existence problems for sequential dynamical systemsDiscrete Math. Theor. Comput. Sci. AB(DMCS)2003698010.46298/dmtcs.2314Search in Google Scholar

[16]C. Barrett, H. B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, M. Thakur, Predecessor existence problems for finite discrete dynamical systems. Theor. Comput. Sci. 386 (1-2) (2007) 3–37.BarrettC.Hunt IIIH. B.MaratheM.V.RaviS.S.RosenkrantzD.J.StearnsR.E.ThakurM.Predecessor existence problems for finite discrete dynamical systemsTheor. Comput. Sci.3861-2200733710.1016/j.tcs.2007.04.026Search in Google Scholar

[17]C. Barrett, H. B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, M. Thakur, Errata for the paper “predecessor existence problems for finite discrete dynamical systems” [theoret. comput. sci. 386 (1-2) (2007) 3-37] (10.1016/j.tcs.2007.04.026), Theor. Comput. Sci. 395 (1) (2008) 132–133.BarrettC.Hunt IIIH. B.MaratheM.V.RaviS.S.RosenkrantzD.J.StearnsR.E.ThakurM.Errata for the paper “predecessor existence problems for finite discrete dynamical systems”theoret. comput. sci.3861-2200733710.1016/j.tcs.2007.04.026Theor. Comput. Sci.39512008132133Open DOISearch in Google Scholar

[18]C. Defant, Binary codes and period-2 orbits of sequential dynamical systems, Discrete Math. Theor. Comput. Sci. 19 (3) (2017), Article number 3971.DefantC.Binary codes and period-2 orbits of sequential dynamical systemsDiscrete Math. Theor. Comput. Sci.1932017Article number 3971Search in Google Scholar

[19]W.Y.C. Chen, X. Li, M.J. Zheng, Matrix method for linear sequential dynamical systems on digraphs, Appl. Math. Comput. 160 (1) (2005), 197–212.ChenW.Y.C.LiX.ZhengM.J.Matrix method for linear sequential dynamical systems on digraphsAppl. Math. Comput.1601200519721210.1016/j.amc.2003.10.023Search in Google Scholar

[20]C. Defant, Binary codes and period-2 orbits of sequential dynamical systems, Discrete Math. Theor. Comput. Sci. 19 (3) (2017), Article number 3971.DefantC.Binary codes and period-2 orbits of sequential dynamical systemsDiscrete Math. Theor. Comput. Sci.1932017Article number 3971Search in Google Scholar

[21]F. Green, NP-complete problems in cellular automata, Complex systems, 1 (3) (1987) 453–474.GreenF.NP-complete problems in cellular automataComplex systems131987453474Search in Google Scholar

[22]A. Kawachi, M. Ogihara, K. Uchizawa, Generalized predecessor existence problems for boolean finite dynamical systems, Paper presented at the Leibniz International Proceedings in Informatics, LIPIcs (2017) 83.KawachiA.OgiharaM.UchizawaK.Generalized predecessor existence problems for boolean finite dynamical systems, Paper presented at the Leibniz International Proceedings in InformaticsLIPIcs201783Search in Google Scholar

[23]Kawachi, A., Ogihara, M., Uchizawa, K. Generalized predecessor existence problems for boolean finite dynamical systems on directed graphs, Theor. Comput. Sci. (2018) (in press)KawachiA.OgiharaM.UchizawaK.Generalized predecessor existence problems for boolean finite dynamical systems on directed graphsTheor. Comput. Sci.2018in press10.1016/j.tcs.2018.08.026Search in Google Scholar

[24]H.S. Mortveit, C.M. Reidys, Discrete, sequential dynamical systems, Discrete Math. 226 (1-3) (2002) 281–295.MortveitH.S.ReidysC.M.Discrete, sequential dynamical systemsDiscrete Math.2261-3200228129510.1016/S0012-365X(00)00115-1Search in Google Scholar

[25]H.S. Mortveit, C.M. Reidys, An introduction to sequential dynamical systems, Springer, New York, 2007.MortveitH.S.ReidysC.M.An introduction to sequential dynamical systemsSpringerNew York2007Search in Google Scholar

[26]M. Ogihara, K. Uchizawa, Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems. In: Jain R., Jain S., Stephan F. (eds) Theory and Applications of Models of Computation. TAMC 2015. Lecture Notes in Computer Science, vol 9076. Springer, Cham, pp. 87–98.OgiharaM.UchizawaK.Computational Complexity Studies of Synchronous Boolean Finite Dynamical SystemsJainR.JainS.StephanF.Theory and Applications of Models of Computation. TAMC 2015. Lecture Notes in Computer Science9076Springer, Cham879810.1007/978-3-319-17142-5_9Search in Google Scholar

[27]M. Ogihara, K. Uchizawa, Computational complexity studies of synchronous boolean finite dynamical systems on directed graphs. Inf. Comput. 256 (2017) 226–236.OgiharaM.UchizawaK.Computational complexity studies of synchronous boolean finite dynamical systems on directed graphsInf. Comput.256201722623610.1016/j.ic.2017.07.008Search in Google Scholar

[28]K. Sutner, On the computational complexity of finite cellular automata, J. Comput. System Sci. 50 (1) (1995) 87–97.SutnerK.On the computational complexity of finite cellular automataJ. Comput. System Sci.5011995879710.1006/jcss.1995.1009Search in Google Scholar