---
_id: '8533'
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.
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."
alternative_title:
- LIPIcs
article_number: 22:1-22:13
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Rasmus
  full_name: Ibsen-Jensen, Rasmus
  id: 3B699956-F248-11E8-B48F-1D18A9856A87
  last_name: Ibsen-Jensen
  orcid: 0000-0003-4783-0389
- first_name: Ismael R
  full_name: Jecker, Ismael R
  id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
  last_name: Jecker
- first_name: Jakub
  full_name: Svoboda, Jakub
  id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
  last_name: Svoboda
  orcid: 0000-0002-1419-3267
citation:
  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>'
  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>'
  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>.'
  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.'
  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.'
  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>.'
  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.
conference:
  end_date: 2020-08-28
  location: Prague, Czech Republic
  name: 'MFCS: Symposium on Mathematical Foundations of Computer Science'
  start_date: 2020-08-24
date_created: 2020-09-20T22:01:36Z
date_published: 2020-08-18T00:00:00Z
date_updated: 2025-06-02T08:53:42Z
day: '18'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.MFCS.2020.22
ec_funded: 1
external_id:
  arxiv:
  - '2007.02894'
file:
- access_level: open_access
  checksum: bbd7c4f55d45f2ff2a0a4ef0e10a77b1
  content_type: application/pdf
  creator: dernst
  date_created: 2020-09-21T13:57:34Z
  date_updated: 2020-09-21T13:57:34Z
  file_id: '8550'
  file_name: 2020_LIPIcs_Chatterjee.pdf
  file_size: 491374
  relation: main_file
  success: 1
file_date_updated: 2020-09-21T13:57:34Z
has_accepted_license: '1'
intvolume: '       170'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: 45th International Symposium on Mathematical Foundations of Computer
  Science
publication_identifier:
  isbn:
  - '9783959771597'
  issn:
  - '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Simplified game of life: Algorithms and complexity'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
  name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
  short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 170
year: '2020'
...
---
_id: '8534'
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.
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."
alternative_title:
- LIPIcs
article_number: 51:1-51:12
article_processing_charge: No
author:
- first_name: Ismael R
  full_name: Jecker, Ismael R
  id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
  last_name: Jecker
- first_name: Orna
  full_name: Kupferman, Orna
  last_name: Kupferman
- first_name: Nicolas
  full_name: Mazzocchi, Nicolas
  last_name: Mazzocchi
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.
  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.'
  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>.
  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.
conference:
  end_date: 2020-08-28
  location: Prague, Czech Republic
  name: 'MFCS: Symposium on Mathematical Foundations of Computer Science'
  start_date: 2020-08-24
date_created: 2020-09-20T22:01:36Z
date_published: 2020-08-18T00:00:00Z
date_updated: 2021-01-12T08:19:56Z
day: '18'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.MFCS.2020.51
ec_funded: 1
file:
- access_level: open_access
  checksum: 2dc9e2fad6becd4563aef3e27a473f70
  content_type: application/pdf
  creator: dernst
  date_created: 2020-09-21T14:17:08Z
  date_updated: 2020-09-21T14:17:08Z
  file_id: '8552'
  file_name: 2020_LIPIcsMFCS_Jecker.pdf
  file_size: 597977
  relation: main_file
  success: 1
file_date_updated: 2020-09-21T14:17:08Z
has_accepted_license: '1'
intvolume: '       170'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: 45th International Symposium on Mathematical Foundations of Computer
  Science
publication_identifier:
  isbn:
  - '9783959771597'
  issn:
  - '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Unary prime languages
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
  name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
  short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 170
year: '2020'
...