pith. machine review for the scientific record. sign in

arxiv: 2605.09937 · v1 · submitted 2026-05-11 · 💻 cs.DC · cs.FL

Recognition: 2 theorem links

· Lean Theorem

Population Protocols over Ordered Agents

Benjamin Courchesne, Corto Mascle, Isa Vialard, Lucie Guillou, Michael Blondin, Micha\"el Cadilhac

Pith reviewed 2026-05-12 03:53 UTC · model grok-4.3

classification 💻 cs.DC cs.FL
keywords population protocolsordered agentsstar-free languagesimmediate observationunambiguous languagesdistributed computingformal language theory
0
0 comments X

The pith

Immediate-observation population protocols over ordered agents recognize exactly the unambiguous star-free languages.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines population protocols in which agents carry unique identifiers that impose a total order, restricting which pairs can interact based on predicates like less-than. Its key result establishes that the immediate-observation fragment with the order predicate, called IO-PP[<], recognizes precisely the unambiguous star-free languages. A reader might care because this class of languages has equivalent definitions in two-variable first-order logic and certain automata, connecting distributed consensus computation to classical language theory. The work also explores how adding predicates like successor affects computational power and the decidability of stabilization.

Core claim

We show that IO-PP[<] recognizes exactly the unambiguous star-free languages. This class has many other characterizations, including two-variable first-order logic and two-way deterministic partially-ordered automata. We provide a logic and an automaton model fitting inside PP[<]. If the successor predicate is added to NSPACE(n)-computable predicates, then IO-PP[N] equals PP[N] equals NSPACE(n). The stabilization problem is undecidable for PP[<] and IO-PP[+1], though conditionally decidable for IO-PP[<].

What carries the argument

The IO-PP[<] model: agents are totally ordered by unique IDs, interactions fire only if one ID is less than the other, and only one agent updates its state per interaction.

If this is right

  • IO-PP[<] protocols can recognize any unambiguous star-free language.
  • The recognized languages coincide with those definable in two-variable first-order logic.
  • Adding the successor predicate to suitable N yields protocols as powerful as NSPACE(n) space-bounded computation.
  • Determining whether a protocol in PP[<] always reaches consensus is undecidable.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Ordering the agents via identifiers offers a lightweight way to enable ordered interactions without full communication of IDs.
  • These results may help in designing distributed systems where agents have partial orderings, such as in sensor networks with positions.
  • Future work could explore whether other simple predicates yield intermediate language classes between regular and star-free.
  • The conditional decidability for IO-PP[<] suggests that the immediate-observation restriction simplifies verification in ordered settings.

Load-bearing premise

The agents are assumed to have distinct unique identifiers inducing a total order, and interactions occur only between pairs whose IDs satisfy the predicate in N, with the population eventually stabilizing to a consensus output.

What would settle it

To falsify the main claim, one would need to find either an unambiguous star-free language that no IO-PP[<] protocol can recognize, or a language recognized by some IO-PP[<] protocol that is not unambiguous and star-free.

read the original abstract

Population protocols are a distributed computation model in which a collection of anonymous, finite-state agents interact in randomly chosen pairs and update their states according to a fixed transition function. The computation is defined by the eventual stabilization of the population to a consensus that represents the output. In practice, it is natural to allow each agent to carry a unique identifier and compare it with that of another agent before interacting. We model this extension by having agents be totally ordered and interactions between two agents to be fireable only if their pair of identifiers falls in some condition set. For instance, $\mathsf{PP}[<]$ allows for two agents to interact only if the first one appears before the second one. We study population protocols over ordered agents $\mathsf{PP}[N]$ where $N$ is a set of predicates available to restrict transition firing. We also study $\textsf{IO-PP}[N]$, the immediate observation fragment of $\mathsf{PP}[N]$ where only one agent changes state per interaction. Our main result is that $\textsf{IO-PP}[<]$ recognizes exactly the unambiguous star-free languages, which admits many other characterizations, such as two-variable first-order logic or two-way deterministic partially-ordered automata. We also provide a logic and an automaton model that fits in $\mathsf{PP}[<]$. We further show that if the successor predicate appears in a set $N$ of $\mathsf{NSPACE}(n)$-computable predicates, then $\textsf{IO-PP}[N]=\mathsf{PP}[N]=\mathsf{NSPACE}(n)$. Finally, we investigate the problem of deciding whether a given population protocol always stabilizes to a consensus. While this problem is decidable for unordered population protocols, we show that this is undecidable already for $\mathsf{PP}[<]$ and $\textsf{IO-PP}[+1]$, but conditionally decidable for $\textsf{IO-PP}[<]$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper extends population protocols to ordered agents with a predicate set N restricting pairwise interactions, defining PP[N] and the immediate-observation fragment IO-PP[N]. The central result is that IO-PP[<] recognizes exactly the unambiguous star-free languages (equivalently, FO² or 2DPPA). It also supplies a logic and automaton model for PP[<], proves that successor in an NSPACE(n)-computable N yields IO-PP[N] = PP[N] = NSPACE(n), and shows undecidability of stabilization for PP[<] and IO-PP[+1] (with conditional decidability for IO-PP[<]).

Significance. If the equivalences hold, the work gives a clean automata-theoretic and logical characterization of a natural ordered fragment of population protocols, linking distributed stabilization to star-free languages and two-variable logic. The NSPACE collapse and stabilization decidability results further map the model's boundaries. These connections are valuable for verification and complexity analysis of identifier-based distributed systems.

minor comments (3)
  1. The abstract and introduction state the main equivalence cleanly, but the manuscript would benefit from an explicit statement (perhaps in §3 or §4) of the precise definition of 'unambiguous' star-free languages used in the proof, to avoid any ambiguity with the standard definition.
  2. In the decidability section, the conditional decidability result for IO-PP[<] is stated but the precise condition (e.g., on the scheduler or on N) should be highlighted in a theorem statement or corollary for immediate visibility.
  3. Figure captions and pseudocode for the automaton constructions could be expanded with one or two concrete examples of state transitions under the ordering predicate to aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work on population protocols over ordered agents, the significance assessment, and the recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation chain for the main result (IO-PP[<] exactly equals the unambiguous star-free languages) proceeds from the explicit model definitions of ordered agents, the N predicate restricting interactions, and the stabilization semantics. Equivalence is established via standard inclusions to known external characterizations (FO², 2DPPA) without any reduction to fitted parameters, self-definitional equations, or load-bearing self-citations. All other claims (NSPACE collapse, undecidability of stabilization) are shown via separate arguments that do not loop back to the central equivalence. The paper is self-contained against external automata/logic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper introduces no free parameters or invented entities. It relies on standard domain assumptions about total orders on agents and predicate-restricted interactions.

axioms (2)
  • domain assumption Agents are totally ordered by unique identifiers.
    Core modeling choice stated in the extension of population protocols to ordered agents.
  • domain assumption Interactions fire only if the pair of identifiers satisfies a predicate from N.
    Defines the PP[N] and IO-PP[N] models.

pith-pipeline@v0.9.0 · 5668 in / 1379 out tokens · 62320 ms · 2026-05-12T03:53:17.410939+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Reference graph

Works this paper leans on

81 extracted references · 81 canonical work pages

  1. [1]

    2006 , publisher =

    Michael Sipser , title =. 2006 , publisher =

    work page 2006

  2. [2]

    Verification of Population Protocols , booktitle =

    Javier Esparza and Pierre Ganty and J. Verification of Population Protocols , booktitle =. 2015 , doi =

    work page 2015

  3. [3]

    Observation Petri Nets , school =

    Chana Weil. Observation Petri Nets , school =

    work page

  4. [4]

    Classic Papers in Combinatorics , pages =

    Ramsey, Frank P , title =. Classic Papers in Combinatorics , pages =. 1987 , doi =

    work page 1987

  5. [5]

    Verification of Immediate Observation Population Protocols , booktitle =

    Javier Esparza and Pierre Ganty and Rupak Majumdar and Chana Weil. Verification of Immediate Observation Population Protocols , booktitle =. 2018 , doi =

    work page 2018

  6. [6]

    Proceedings of the London Mathematical Society , volume =

    Higman, Graham , title =. Proceedings of the London Mathematical Society , volume =. 1952 , doi =

    work page 1952

  7. [7]

    2018 , url =

    Simon Halfon , title =. 2018 , url =

    work page 2018

  8. [8]

    Michael Raskin , title =. Proc.\. 2024 , doi =

    work page 2024

  9. [9]

    2023 , isbn =

    Javier Esparza and Michael Blondin , title =. 2023 , isbn =

    work page 2023

  10. [10]

    Hiroto Yasumi and Fukuhito Ooshita and Michiko Inoue , title =. Proc.\. 2021 , doi =

    work page 2021

  11. [11]

    Fischer and Hong Jiang and Ren

    Dana Angluin and James Aspnes and Melody Chan and Michael J. Fischer and Hong Jiang and Ren. Stably Computable Properties of Network Graphs , booktitle =. 2005 , doi =

    work page 2005

  12. [12]

    Verification of Population Protocols with Unordered Data , booktitle =

    Steffen van Bergerem and Roland Guttenberg and Sandra Kiefer and Corto Mascle and Nicolas Waldburger and Chana Weil. Verification of Population Protocols with Unordered Data , booktitle =. 2024 , doi =

    work page 2024

  13. [13]

    Population Protocols with Unordered Data , booktitle =

    Michael Blondin and Fran. Population Protocols with Unordered Data , booktitle =. 2023 , doi =

    work page 2023

  14. [14]

    Spirakis , title =

    Othon Michail and Ioannis Chatzigiannakis and Paul G. Spirakis , title =. Theoretical Computer Science , volume =. 2011 , doi =

    work page 2011

  15. [15]

    Middleware for Network Eccentric and Mobile Applications , pages =

    James Aspnes and Eric Ruppert , title =. Middleware for Network Eccentric and Mobile Applications , pages =. 2009 , doi =

    work page 2009

  16. [16]

    A simple game for the study of trust in distributed systems , journal =

    Diamadi, Zo. A simple game for the study of trust in distributed systems , journal =. 2001 , doi =

    work page 2001

  17. [17]

    Deterministic function computation with chemical reaction networks , journal =

    Ho. Deterministic function computation with chemical reaction networks , journal =. 2014 , doi =

    work page 2014

  18. [18]

    Distributed Computing , volume =

    Dana Angluin and James Aspnes and David Eisenstat and Eric Ruppert , title =. Distributed Computing , volume =. 2007 , doi =

    work page 2007

  19. [19]

    Adam Ganczorz and Leszek Gasieniec and Tomasz Jurdzinski and Jakub Kowalski and Grzegorz Stachowiak , title =. Proc.\. 2024 , doi =

    work page 2024

  20. [20]

    Homonym Population Protocols , journal =

    Olivier Bournez and Johanne Cohen and Mika. Homonym Population Protocols , journal =. 2018 , doi =

    work page 2018

  21. [21]

    Rachid Guerraoui and Eric Ruppert , title =. Proc.\. 2009 , doi =

    work page 2009

  22. [22]

    Over Words, Two Variables Are as Powerful as One Quantifier Alternation , booktitle =

    Denis Th. Over Words, Two Variables Are as Powerful as One Quantifier Alternation , booktitle =. 1998 , doi =

    work page 1998

  23. [23]

    Vardi and Thomas Wilke , title =

    Kousha Etessami and Moshe Y. Vardi and Thomas Wilke , title =. Information and Computation , volume =. 2002 , doi =

    work page 2002

  24. [24]

    Polynomial Closure and Unambiguous Product , booktitle =

    Jean. Polynomial Closure and Unambiguous Product , booktitle =. 1995 , doi =

    work page 1995

  25. [25]

    Sur le produit de concat

    Sch. Sur le produit de concat. Semigroup Forum , volume =. 1976 , doi =

    work page 1976

  26. [26]

    Partially-Ordered Two-Way Automata:

    Thomas Schwentick and Denis Th. Partially-Ordered Two-Way Automata:. Proc.\. 2001 , doi =

    work page 2001

  27. [27]

    1999 , doi =

    Aldo de Luca and Stefano Varricchio , title =. 1999 , doi =

    work page 1999

  28. [28]

    Diamonds are forever: The variety

    Tesson, Pascal and Th. Diamonds are forever: The variety. Semigroups, algorithms, automata and languages , publisher =. 2002 , doi =

    work page 2002

  29. [29]

    Computation in networks of passively mobile finite-state sensors , journal =

    Dana Angluin and James Aspnes and Zo. Computation in networks of passively mobile finite-state sensors , journal =. 2006 , doi =

    work page 2006

  30. [30]

    Pandya and Simoni S

    Kamal Lodaya and Paritosh K. Pandya and Simoni S. Shah , title =. Proc.\. 2010 , doi =

    work page 2010

  31. [31]

    Philipp Weis and Neil Immerman , title =. Proc.\. 2007 , doi =

    work page 2007

  32. [32]

    Classes of Languages and Linear-Bounded Automata , journal =

    Sige. Classes of Languages and Linear-Bounded Automata , journal =. 1964 , doi =

    work page 1964

  33. [33]

    Syntactic Semigroups , booktitle =

    Jean. Syntactic Semigroups , booktitle =. 1997 , doi =

    work page 1997

  34. [34]

    Andres Montoya , title =

    J. Andres Montoya , title =. Proc.\. 2025 , doi =

    work page 2025

  35. [35]

    Alin Bostan and Arnaud Carayol and Florent Koechlin and Cyril Nicaud , title =. Proc.\. 2020 , doi =

    work page 2020

  36. [36]

    Unambiguous constrained Automata , journal =

    Micha. Unambiguous constrained Automata , journal =. 2013 , doi =

    work page 2013

  37. [37]

    Emmanuel Filiot and Shibashis Guha and Nicolas Mazzocchi , title =. Proc.\. 2019 , doi =

    work page 2019

  38. [38]

    , title =

    Lothaire, M. , title =

    work page

  39. [39]

    TheoretiCS , volume =

    Thomas Place and Marc Zeitoun , title =. TheoretiCS , volume =. 2023 , doi =

    work page 2023

  40. [40]

    Anil Ada , title =. Proc.\. 2008 , doi =

    work page 2008

  41. [41]

    Regular languages and partial commutations , journal =

    Antonio Cano G. Regular languages and partial commutations , journal =. 2013 , doi =

    work page 2013

  42. [42]

    On the non-deterministic communication complexity of regular languages

    Anil Ada. On the non-deterministic communication complexity of regular languages. In Proc.\ 12 ^ th International Conference on Developments in Language Theory ( DLT ) , pages 96--107, 2008. https://doi.org/10.1007/978-3-540-85780-8_7 doi:10.1007/978-3-540-85780-8_7

    work page doi:10.1007/978-3-540-85780-8_7 2008

  43. [43]

    Fischer, Hong Jiang, and Ren \' e Peralta

    Dana Angluin, James Aspnes, Melody Chan, Michael J. Fischer, Hong Jiang, and Ren \' e Peralta. Stably computable properties of network graphs. In First IEEE International Conference on Distributed Computing in Sensor Systems ( DCOSS ) , pages 63--74, 2005. https://doi.org/10.1007/11502593_8 doi:10.1007/11502593_8

    work page doi:10.1007/11502593_8 2005

  44. [44]

    Fischer, and Ren \' e Peralta

    Dana Angluin, James Aspnes, Zo \" e Diamadi, Michael J. Fischer, and Ren \' e Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing , 18(4):235--253, 2006. https://doi.org/10.1007/s00446-005-0138-3 doi:10.1007/s00446-005-0138-3

    work page doi:10.1007/s00446-005-0138-3 2006

  45. [45]

    The computational power of population protocols

    Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing , 20(4):279--304, 2007. https://doi.org/10.1007/s00446-007-0040-2 doi:10.1007/s00446-007-0040-2

    work page doi:10.1007/s00446-007-0040-2 2007

  46. [46]

    An introduction to population protocols

    James Aspnes and Eric Ruppert. An introduction to population protocols. In Middleware for Network Eccentric and Mobile Applications , pages 97--120. Springer, 2009. https://doi.org/10.1007/978-3-540-89707-1_5 doi:10.1007/978-3-540-89707-1_5

    work page doi:10.1007/978-3-540-89707-1_5 2009

  47. [47]

    Population protocols with unordered data

    Michael Blondin and Fran c ois Ladouceur. Population protocols with unordered data. In Proc.\ 50 ^ th International Colloquium on Automata, Languages, and Programming ( ICALP ) , pages 115:1--115:20, 2023. https://doi.org/10.4230/LIPICS.ICALP.2023.115 doi:10.4230/LIPICS.ICALP.2023.115

    work page doi:10.4230/lipics.icalp.2023.115 2023

  48. [48]

    Weakly-unambiguous P arikh automata and their link to holonomic series

    Alin Bostan, Arnaud Carayol, Florent Koechlin, and Cyril Nicaud. Weakly-unambiguous P arikh automata and their link to holonomic series. In Proc.\ 47 ^ th International Colloquium on Automata, Languages, and Programming ( ICALP ) , pages 114:1--114:16, 2020. https://doi.org/10.4230/LIPICS.ICALP.2020.114 doi:10.4230/LIPICS.ICALP.2020.114

    work page doi:10.4230/lipics.icalp.2020.114 2020

  49. [49]

    Homonym population protocols

    Olivier Bournez, Johanne Cohen, and Mika \" e l Rabie. Homonym population protocols. Theory of Computing Systems , 62(5):1318--1346, 2018. https://doi.org/10.1007/S00224-017-9833-2 doi:10.1007/S00224-017-9833-2

    work page doi:10.1007/s00224-017-9833-2 2018

  50. [50]

    Unambiguous constrained automata

    Micha \" e l Cadilhac, Alain Finkel, and Pierre McKenzie. Unambiguous constrained automata. International Journal of Foundations of Computer Science , 24(7):1099--1116, 2013. https://doi.org/10.1142/S0129054113400339 doi:10.1142/S0129054113400339

    work page doi:10.1142/s0129054113400339 2013

  51. [51]

    Deterministic function computation with chemical reaction networks

    Ho - Lin Chen, David Doty, and David Soloveichik. Deterministic function computation with chemical reaction networks. Natural Computing , 13(4):517--534, 2014. https://doi.org/10.1007/S11047-013-9393-6 doi:10.1007/S11047-013-9393-6

    work page doi:10.1007/s11047-013-9393-6 2014

  52. [52]

    A simple game for the study of trust in distributed systems

    Zo \"e Diamadi and Michael J Fischer. A simple game for the study of trust in distributed systems. Wuhan University Journal of Natural Sciences , 6(1):72--82, 2001. https://doi.org/10.1007/BF03160228 doi:10.1007/BF03160228

    work page doi:10.1007/bf03160228 2001

  53. [53]

    Automata theory: An algorithmic approach

    Javier Esparza and Michael Blondin. Automata theory: An algorithmic approach . The MIT Press, 2023

    work page 2023

  54. [54]

    Verification of population protocols

    Javier Esparza, Pierre Ganty, J \' e r \^ o me Leroux, and Rupak Majumdar. Verification of population protocols. In Proc.\ 26 ^ th International Conference on Concurrency Theory ( CONCUR ) , pages 470--482, 2015. https://doi.org/10.4230/LIPICS.CONCUR.2015.470 doi:10.4230/LIPICS.CONCUR.2015.470

    work page doi:10.4230/lipics.concur.2015.470 2015

  55. [55]

    Verification of immediate observation population protocols

    Javier Esparza, Pierre Ganty, Rupak Majumdar, and Chana Weil - Kennedy. Verification of immediate observation population protocols. In Proc.\ 29 ^ th International Conference on Concurrency Theory ( CONCUR ) , volume 118, pages 31:1--31:16, 2018. https://doi.org/10.4230/LIPICS.CONCUR.2018.31 doi:10.4230/LIPICS.CONCUR.2018.31

    work page doi:10.4230/lipics.concur.2018.31 2018

  56. [56]

    Vardi, and Thomas Wilke

    Kousha Etessami, Moshe Y. Vardi, and Thomas Wilke. First-order logic with two variables and unary temporal logic. Information and Computation , 179(2):279--295, 2002. https://doi.org/10.1006/INCO.2001.2953 doi:10.1006/INCO.2001.2953

    work page doi:10.1006/inco.2001.2953 2002

  57. [57]

    Two-way P arikh automata

    Emmanuel Filiot, Shibashis Guha, and Nicolas Mazzocchi. Two-way P arikh automata. In Proc.\ 39 ^ th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science ( FSTTCS ) , pages 40:1--40:14, 2019. https://doi.org/10.4230/LIPICS.FSTTCS.2019.40 doi:10.4230/LIPICS.FSTTCS.2019.40

    work page doi:10.4230/lipics.fsttcs.2019.40 2019

  58. [58]

    Selective population protocols

    Adam Ganczorz, Leszek Gasieniec, Tomasz Jurdzinski, Jakub Kowalski, and Grzegorz Stachowiak. Selective population protocols. In Proc.\ 26 ^ th International Symposium on Stabilization, Safety, and Security of Distributed Systems ( SSS ) , pages 225--239, 2024. https://doi.org/10.1007/978-3-031-74498-3_16 doi:10.1007/978-3-031-74498-3_16

    work page doi:10.1007/978-3-031-74498-3_16 2024

  59. [59]

    Regular languages and partial commutations

    Antonio Cano G \' o mez, Giovanna Guaiana, and Jean - \' E ric Pin. Regular languages and partial commutations. Information and Computation , 230:76--96, 2013. https://doi.org/10.1016/J.IC.2013.07.003 doi:10.1016/J.IC.2013.07.003

    work page doi:10.1016/j.ic.2013.07.003 2013

  60. [60]

    Names trump malice: Tiny mobile agents can tolerate B yzantine failures

    Rachid Guerraoui and Eric Ruppert. Names trump malice: Tiny mobile agents can tolerate B yzantine failures. In Proc.\ 36 ^ th International Colloquium Automata, Languages and Programming ( ICALP ) , pages 484--495, 2009. https://doi.org/10.1007/978-3-642-02930-1_40 doi:10.1007/978-3-642-02930-1_40

    work page doi:10.1007/978-3-642-02930-1_40 2009

  61. [61]

    On Effective Representations of Well Quasi-Orderings

    Simon Halfon. On Effective Representations of Well Quasi-Orderings. (Repr \' e sentations Effectives des Beaux Pr \' e -Ordres) . PhD thesis, Université Paris-Saclay, France, 2018. URL: https://tel.archives-ouvertes.fr/tel-01945232

    work page 2018

  62. [62]

    Ordering by divisibility in abstract algebras

    Graham Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society , s3-2(1):326--336, 1952. https://doi.org/10.1112/plms/s3-2.1.326 doi:10.1112/plms/s3-2.1.326

    work page doi:10.1112/plms/s3-2.1.326 1952

  63. [63]

    Classes of languages and linear-bounded automata

    Sige - Yuki Kuroda. Classes of languages and linear-bounded automata. Information and Control , 7(2):207--223, 1964. https://doi.org/10.1016/S0019-9958(64)90120-2 doi:10.1016/S0019-9958(64)90120-2

    work page doi:10.1016/s0019-9958(64)90120-2 1964

  64. [64]

    Pandya, and Simoni S

    Kamal Lodaya, Paritosh K. Pandya, and Simoni S. Shah. Around dot depth two. In Proc.\ 14 ^ th International Conference on Developments in Language Theory ( DLT ) , pages 303--315, 2010. https://doi.org/10.1007/978-3-642-14455-4_28 doi:10.1007/978-3-642-14455-4_28

    work page doi:10.1007/978-3-642-14455-4_28 2010

  65. [65]

    Lothaire

    M. Lothaire. Algebraic Combinatorics on Words . Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002

    work page 2002

  66. [66]

    Spirakis

    Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis. Mediated population protocols. Theoretical Computer Science , 412(22):2434--2450, 2011. https://doi.org/10.1016/J.TCS.2011.02.003 doi:10.1016/J.TCS.2011.02.003

    work page doi:10.1016/j.tcs.2011.02.003 2011

  67. [67]

    Andres Montoya

    J. Andres Montoya. Asymptotic reasoning with two variables. In Proc.\ 31 ^ st International Workshop on Logic, Language, Information, and Computation ( WoLLIC ) , pages 38--55, 2025. https://doi.org/10.1007/978-3-031-99536-1_3 doi:10.1007/978-3-031-99536-1_3

    work page doi:10.1007/978-3-031-99536-1_3 2025

  68. [68]

    Syntactic semigroups

    Jean - \'E ric Pin. Syntactic semigroups. In Handbook of Formal Languages, Volume 1: Word, Language, Grammar , pages 679--746. Springer, 1997. https://doi.org/10.1007/978-3-642-59136-5_10 doi:10.1007/978-3-642-59136-5_10

    work page doi:10.1007/978-3-642-59136-5_10 1997

  69. [69]

    Polynomial closure and unambiguous product

    Jean - \' E ric Pin and Pascal Weil. Polynomial closure and unambiguous product. In Proc.\ 22 ^ nd International Colloquium on Automata, Languages and Programming ( ICALP ) , pages 348--359, 1995. https://doi.org/10.1007/3-540-60084-1_87 doi:10.1007/3-540-60084-1_87

    work page doi:10.1007/3-540-60084-1_87 1995

  70. [70]

    All about unambiguous polynomial closure

    Thomas Place and Marc Zeitoun. All about unambiguous polynomial closure. TheoretiCS , 2, 2023. https://doi.org/10.46298/THEORETICS.23.11 doi:10.46298/THEORETICS.23.11

    work page doi:10.46298/theoretics.23.11 2023

  71. [71]

    On a problem of formal logic

    Frank P Ramsey. On a problem of formal logic. In Classic Papers in Combinatorics , pages 1--24. Springer, 1987. https://doi.org/10.1007/978-0-8176-4842-8_1 doi:10.1007/978-0-8176-4842-8_1

    work page doi:10.1007/978-0-8176-4842-8_1 1987

  72. [72]

    Modular population protocols

    Michael Raskin. Modular population protocols. In Proc.\ 20 ^ th International Symposium on Algorithmics of Wireless Networks ( ALGOWIN ) , pages 173--187, 2024. https://doi.org/10.1007/978-3-031-74580-5_13 doi:10.1007/978-3-031-74580-5_13

    work page doi:10.1007/978-3-031-74580-5_13 2024

  73. [73]

    u tzenberger. Sur le produit de concat \'e nation non ambig \

    Marcel-Paul Sch \"u tzenberger. Sur le produit de concat \'e nation non ambig \"u . Semigroup Forum , 13(1):47--75, 1976. https://doi.org/10.1007/bf02194921 doi:10.1007/bf02194921

    work page doi:10.1007/bf02194921 1976

  74. [74]

    Partially-ordered two-way automata: A new characterization of DA

    Thomas Schwentick, Denis Th \' e rien, and Heribert Vollmer. Partially-ordered two-way automata: A new characterization of DA . In Proc.\ 5 ^ th International Conference on Developments in Language Theory ( DLT ) , pages 239--250, 2001. https://doi.org/10.1007/3-540-46011-X_20 doi:10.1007/3-540-46011-X_20

    work page doi:10.1007/3-540-46011-x_20 2001

  75. [75]

    Introduction to the theory of computation

    Michael Sipser. Introduction to the theory of computation . Thomson Course Technology, second edition, 2006

    work page 2006

  76. [76]

    Diamonds are forever: The variety DA

    Pascal Tesson and Denis Th \'e rien. Diamonds are forever: The variety DA . In Semigroups, algorithms, automata and languages , pages 475--499. World Scientific, 2002. https://doi.org/10.1142/5050 doi:10.1142/5050

    work page doi:10.1142/5050 2002

  77. [77]

    Over words, two variables are as powerful as one quantifier alternation

    Denis Th \' e rien and Thomas Wilke. Over words, two variables are as powerful as one quantifier alternation. In Proc.\ 30 ^ th Annual ACM Symposium on the Theory of Computing ( STOC ) , pages 234--240, 1998. https://doi.org/10.1145/276698.276749 doi:10.1145/276698.276749

    work page doi:10.1145/276698.276749 1998

  78. [78]

    Verification of population protocols with unordered data

    Steffen van Bergerem, Roland Guttenberg, Sandra Kiefer, Corto Mascle, Nicolas Waldburger, and Chana Weil - Kennedy. Verification of population protocols with unordered data. In Proc.\ 51 ^ st International Colloquium on Automata, Languages, and Programming ( ICALP ) , pages 156:1--156:20, 2024. https://doi.org/10.4230/LIPICS.ICALP.2024.156 doi:10.4230/LIP...

    work page doi:10.4230/lipics.icalp.2024.156 2024

  79. [79]

    Observation Petri Nets

    Chana Weil - Kennedy. Observation Petri Nets . PhD thesis, Technical University of Munich, Germany, 2023

    work page 2023

  80. [80]

    Structure theorem and strict alternation hierarchy for FO ^ 2 on words

    Philipp Weis and Neil Immerman. Structure theorem and strict alternation hierarchy for FO ^ 2 on words. In Proc.\ 21 ^ st International Workshop on Computer Science Logic ( CSL ) , pages 343--357, 2007. https://doi.org/10.1007/978-3-540-74915-8_27 doi:10.1007/978-3-540-74915-8_27

    work page doi:10.1007/978-3-540-74915-8_27 2007

Showing first 80 references.