[{"file_date_updated":"2020-09-21T13:57:34Z","quality_controlled":"1","ec_funded":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Jecker, Ismael R","first_name":"Ismael R","last_name":"Jecker","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425"},{"first_name":"Jakub","last_name":"Svoboda","orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"}],"_id":"8533","license":"https://creativecommons.org/licenses/by/3.0/","scopus_import":"1","alternative_title":["LIPIcs"],"title":"Simplified game of life: Algorithms and complexity","intvolume":"       170","publication_status":"published","article_processing_charge":"No","date_created":"2020-09-20T22:01:36Z","department":[{"_id":"KrCh"}],"ddc":["000"],"acknowledgement":"Krishnendu Chatterjee: The research was partially supported by the Vienna Science and\r\nTechnology Fund (WWTF) Project ICT15-003.\r\nIsmaël Jecker: This project has received funding from the European Union’s Horizon 2020 research\r\nand innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411.","volume":170,"external_id":{"arxiv":["2007.02894"]},"date_updated":"2025-06-02T08:53:42Z","citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, I.R. Jecker, J. Svoboda, in:, 45th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Chatterjee, Krishnendu, et al. “Simplified Game of Life: Algorithms and Complexity.” <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 170, 22:1-22:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">10.4230/LIPIcs.MFCS.2020.22</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. 2020. Simplified game of life: Algorithms and complexity. 45th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 170, 22:1-22:13.","apa":"Chatterjee, K., Ibsen-Jensen, R., Jecker, I. R., &#38; Svoboda, J. (2020). Simplified game of life: Algorithms and complexity. In <i>45th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 170). Prague, Czech Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">https://doi.org/10.4230/LIPIcs.MFCS.2020.22</a>","ama":"Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. Simplified game of life: Algorithms and complexity. In: <i>45th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">10.4230/LIPIcs.MFCS.2020.22</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, I. R. Jecker, and J. Svoboda, “Simplified game of life: Algorithms and complexity,” in <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Prague, Czech Republic, 2020, vol. 170.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Ismael R Jecker, and Jakub Svoboda. “Simplified Game of Life: Algorithms and Complexity.” In <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">https://doi.org/10.4230/LIPIcs.MFCS.2020.22</a>."},"year":"2020","abstract":[{"lang":"eng","text":"Game of Life is a simple and elegant model to study dynamical system over networks. The model consists of a graph where every vertex has one of two types, namely, dead or alive. A configuration is a mapping of the vertices to the types. An update rule describes how the type of a vertex is updated given the types of its neighbors. In every round, all vertices are updated synchronously, which leads to a configuration update. While in general, Game of Life allows a broad range of update rules, we focus on two simple families of update rules, namely, underpopulation and overpopulation, that model several interesting dynamics studied in the literature. In both settings, a dead vertex requires at least a desired number of live neighbors to become alive. For underpopulation (resp., overpopulation), a live vertex requires at least (resp. at most) a desired number of live neighbors to remain alive. We study the basic computation problems, e.g., configuration reachability, for these two families of rules. For underpopulation rules, we show that these problems can be solved in polynomial time, whereas for overpopulation rules they are PSPACE-complete."}],"doi":"10.4230/LIPIcs.MFCS.2020.22","arxiv":1,"day":"18","language":[{"iso":"eng"}],"conference":{"end_date":"2020-08-28","location":"Prague, Czech Republic","name":"MFCS: Symposium on Mathematical Foundations of Computer Science","start_date":"2020-08-24"},"publication":"45th International Symposium on Mathematical Foundations of Computer Science","has_accepted_license":"1","month":"08","article_number":"22:1-22:13","oa_version":"Published Version","project":[{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"},{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","file":[{"creator":"dernst","file_id":"8550","relation":"main_file","success":1,"access_level":"open_access","file_name":"2020_LIPIcs_Chatterjee.pdf","content_type":"application/pdf","date_updated":"2020-09-21T13:57:34Z","file_size":491374,"checksum":"bbd7c4f55d45f2ff2a0a4ef0e10a77b1","date_created":"2020-09-21T13:57:34Z"}],"date_published":"2020-08-18T00:00:00Z","type":"conference","tmp":{"name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","image":"/images/cc_by.png","short":"CC BY (3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"oa":1,"publication_identifier":{"issn":["18688969"],"isbn":["9783959771597"]}},{"article_number":"51:1-51:12","month":"08","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"oa_version":"Published Version","has_accepted_license":"1","publication":"45th International Symposium on Mathematical Foundations of Computer Science","conference":{"end_date":"2020-08-28","location":"Prague, Czech Republic","start_date":"2020-08-24","name":"MFCS: Symposium on Mathematical Foundations of Computer Science"},"language":[{"iso":"eng"}],"oa":1,"publication_identifier":{"issn":["18688969"],"isbn":["9783959771597"]},"type":"conference","date_published":"2020-08-18T00:00:00Z","tmp":{"name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","image":"/images/cc_by.png","short":"CC BY (3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","file":[{"success":1,"relation":"main_file","access_level":"open_access","file_id":"8552","creator":"dernst","date_created":"2020-09-21T14:17:08Z","checksum":"2dc9e2fad6becd4563aef3e27a473f70","file_size":597977,"date_updated":"2020-09-21T14:17:08Z","content_type":"application/pdf","file_name":"2020_LIPIcsMFCS_Jecker.pdf"}],"intvolume":"       170","alternative_title":["LIPIcs"],"title":"Unary prime languages","article_processing_charge":"No","date_created":"2020-09-20T22:01:36Z","department":[{"_id":"KrCh"}],"publication_status":"published","author":[{"first_name":"Ismael R","last_name":"Jecker","full_name":"Jecker, Ismael R","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425"},{"last_name":"Kupferman","first_name":"Orna","full_name":"Kupferman, Orna"},{"last_name":"Mazzocchi","first_name":"Nicolas","full_name":"Mazzocchi, Nicolas"}],"scopus_import":"1","_id":"8534","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2020-09-21T14:17:08Z","ec_funded":1,"quality_controlled":"1","abstract":[{"lang":"eng","text":"A regular language L of finite words is composite if there are regular languages L₁,L₂,…,L_t such that L = ⋂_{i = 1}^t L_i and the index (number of states in a minimal DFA) of every language L_i is strictly smaller than the index of L. Otherwise, L is prime. Primality of regular languages was introduced and studied in [O. Kupferman and J. Mosheiff, 2015], where the complexity of deciding the primality of the language of a given DFA was left open, with a doubly-exponential gap between the upper and lower bounds. We study primality for unary regular languages, namely regular languages with a singleton alphabet. A unary language corresponds to a subset of ℕ, making the study of unary prime languages closer to that of primality in number theory. We show that the setting of languages is richer. In particular, while every composite number is the product of two smaller numbers, the number t of languages necessary to decompose a composite unary language induces a strict hierarchy. In addition, a primality witness for a unary language L, namely a word that is not in L but is in all products of languages that contain L and have an index smaller than L’s, may be of exponential length. Still, we are able to characterize compositionality by structural properties of a DFA for L, leading to a LogSpace algorithm for primality checking of unary DFAs."}],"day":"18","doi":"10.4230/LIPIcs.MFCS.2020.51","year":"2020","citation":{"ama":"Jecker IR, Kupferman O, Mazzocchi N. Unary prime languages. In: <i>45th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">10.4230/LIPIcs.MFCS.2020.51</a>","apa":"Jecker, I. R., Kupferman, O., &#38; Mazzocchi, N. (2020). Unary prime languages. In <i>45th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 170). Prague, Czech Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">https://doi.org/10.4230/LIPIcs.MFCS.2020.51</a>","chicago":"Jecker, Ismael R, Orna Kupferman, and Nicolas Mazzocchi. “Unary Prime Languages.” In <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">https://doi.org/10.4230/LIPIcs.MFCS.2020.51</a>.","ieee":"I. R. Jecker, O. Kupferman, and N. Mazzocchi, “Unary prime languages,” in <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Prague, Czech Republic, 2020, vol. 170.","short":"I.R. Jecker, O. Kupferman, N. Mazzocchi, in:, 45th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Jecker, Ismael R., et al. “Unary Prime Languages.” <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 170, 51:1-51:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">10.4230/LIPIcs.MFCS.2020.51</a>.","ista":"Jecker IR, Kupferman O, Mazzocchi N. 2020. Unary prime languages. 45th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 170, 51:1-51:12."},"date_updated":"2021-01-12T08:19:56Z","ddc":["000"],"acknowledgement":"Ismaël Jecker: This project has received funding from the European Union’s Horizon\r\n2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.\r\n754411. Nicolas Mazzocchi: PhD fellowship FRIA from the F.R.S.-FNRS.","volume":170}]