pith. machine review for the scientific record. sign in

arxiv: 2605.09435 · v1 · submitted 2026-05-10 · 💻 cs.FL

Recognition: 3 theorem links

· Lean Theorem

Star Complexity of Parikh Images of Languages over Infinite Alphabets

Yoav Danieli
Authors on Pith no claims yet

Pith reviewed 2026-05-12 02:38 UTC · model grok-4.3

classification 💻 cs.FL
keywords register automataParikh imagesinfinite alphabetsstar-heightParikh theoremcontext-free languagescommutative images
0
0 comments X

The pith

The Parikh image of languages recognized by multi-register automata over infinite alphabets is not always rational.

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

This paper examines whether the commutative Parikh image of every language recognized by a register automaton over an infinite alphabet is always definable by a rational expression. It proves a refinement for the one-register case: the star-height of such images is bounded by two. It further shows that one-register context-free languages can produce rational commutative images of arbitrarily high star-height. The central advance is a disproof of the general conjecture for multiple registers together with a separation showing that context-free grammars and automata have unequal commutative expressive power over infinite alphabets.

Core claim

The paper proves that the star-height of the Parikh image of any language recognized by a one-register automaton is universally bounded by two. It shows that one-register context-free languages have rational commutative images of arbitrarily high star-height. It then gives counterexamples establishing that the conjecture fails for automata with multiple registers and that the commutative expressive power of context-free grammars and automata over infinite alphabets are not equivalent.

What carries the argument

The Parikh image, the commutative projection of the accepted language, together with the star-height of rational expressions over the semiring of multisets; the mechanism is the analysis of register automata that perform equality tests and assignments on an infinite alphabet.

If this is right

  • The star-height of Parikh images for languages recognized by one-register automata is at most two.
  • One-register context-free languages can have Parikh images whose rational expressions require arbitrarily high star-height.
  • There exist languages recognized by multi-register automata whose Parikh images are not rational.
  • The commutative expressive power of context-free grammars differs from that of register automata over infinite alphabets.

Where Pith is reading between the lines

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

  • The number of registers appears to determine whether the commutative image remains rational.
  • Decision procedures for properties of these languages may need separate handling for different register counts.
  • Other classical results from finite alphabets may require similar adjustments when the alphabet is infinite.

Load-bearing premise

That the Parikh image is the standard commutative projection and that rationality of the resulting expression is defined in the usual way over the appropriate semiring.

What would settle it

A concrete language accepted by a two-register automaton whose Parikh image cannot be expressed by any rational expression.

Figures

Figures reproduced from arXiv: 2605.09435 by Yoav Danieli.

Figure 5
Figure 5. Figure 5: a , b, c n1 a , d n2 e , f, c n3 e , g n4 h, c n5 [PITH_FULL_IMAGE:figures/full_fig_p044_5.png] view at source ↗
read the original abstract

It has been conjectured that the Parikh (commutative) image of every language over an infinite alphabet recognized by an automaton with registers is defined by a rational expression. This conjecture is known to hold for all languages recognized by one-register automata. We refine this result by proving that the star-height of the Parikh image of any language recognized by a one-register automaton is universally bounded by two. Furthermore, we show that one-register context-free languages have rational commutative images of arbitrarily high star height. We then disprove the conjecture for multiple registers, as well as disprove the equivalence of commutative expressive power between context-free grammars and automata over infinite alphabets. In other words, we show that Parikh's theorem fails for infinite alphabets.

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

1 major / 0 minor

Summary. The paper addresses a conjecture that the Parikh (commutative) image of every language recognized by a register automaton over an infinite alphabet is rational. It refines the known one-register case by proving that the star-height of such Parikh images is universally bounded by two. It shows that one-register context-free languages have rational Parikh images of arbitrarily high star-height. The paper then supplies counterexamples disproving the conjecture for automata with multiple registers and disproving the equivalence of commutative expressive power between context-free grammars and automata over infinite alphabets, concluding that Parikh's theorem fails in this setting.

Significance. If the stated proofs and explicit counterexamples hold, the universal star-height bound of two for one-register automata provides a precise refinement of prior rationality results, while the separations for multi-register automata and between CFGs and automata constitute concrete negative resolutions of conjectures. These results would be significant for the theory of automata and languages over infinite alphabets, clarifying the limits of commutative images and the distinctions between model classes.

major comments (1)
  1. The central claims rest on the existence of a proof that the star-height is bounded by two for one-register automata and on explicit counterexample languages for the multi-register case and the CFG-automaton separation. The abstract asserts these results but supplies no derivations, automaton constructions, or verification steps for the bound or the counterexamples; without these details the load-bearing claims cannot be assessed for correctness.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their summary of the paper and for identifying the need for sufficient detail to evaluate the central claims. We address the major comment below.

read point-by-point responses

  1. Referee: The central claims rest on the existence of a proof that the star-height is bounded by two for one-register automata and on explicit counterexample languages for the multi-register case and the CFG-automaton separation. The abstract asserts these results but supplies no derivations, automaton constructions, or verification steps for the bound or the counterexamples; without these details the load-bearing claims cannot be assessed for correctness.

    Authors: The abstract is intended only as a high-level summary. The full manuscript supplies the required details: the proof that the star-height of Parikh images is at most two for any one-register automaton appears in Section 3, with complete derivations establishing the bound via induction on the structure of the automaton and analysis of the possible commutative images. Section 4 contains explicit multi-register automata together with the languages they recognize and step-by-step verification that the corresponding Parikh images are not rational, thereby disproving the conjecture. Section 5 provides concrete context-free grammars and register automata whose commutative images differ, with full proofs of the separation. These sections include all derivations, constructions, and verification arguments needed to assess the claims. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives a universal star-height bound of two for Parikh images of one-register automaton languages directly from the standard register-automaton model and Parikh-image definitions taken from prior literature. It supplies explicit counterexample languages to refute the multi-register conjecture and the claimed CFG-automaton equivalence over infinite alphabets. No load-bearing step reduces by construction to a fitted parameter, self-definition, or unverified self-citation chain; all central claims rest on independent constructions against external benchmarks rather than renaming or re-deriving the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard mathematical properties of rational expressions and star-height together with the established model of register automata; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • standard math Properties of star-height and rational expressions over commutative monoids or semirings
    Used to define and measure the complexity of Parikh images.
  • domain assumption Register automata with equality tests and assignments over infinite alphabets follow the standard model in the literature
    The one-register case and its extension to multiple registers presuppose this model.

pith-pipeline@v0.9.0 · 5413 in / 1430 out tokens · 89943 ms · 2026-05-12T02:38:00.655743+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.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

76 extracted references · 76 canonical work pages

  1. [1]

    Bar-Hillel and M

    Y. Bar-Hillel and M. Perles and E. Shamir , title =. Zeitschrift f\". 1961 , pages =

    work page 1961

  2. [2]

    Automata, Languages and Programming, 29th International Colloquium,

    Michal Bielecki and Jan Hidders and Jan Paredaens and Jerzy Tyszkiewicz and Jan Van den Bussche , title =. Automata, Languages and Programming, 29th International Colloquium,. 2002 , pages =. doi:10.1007/3-540-45465-9_65 , url =

    work page doi:10.1007/3-540-45465-9_65 2002

  3. [3]

    21st Annual IEEE Symposium on Logic in Computer Science (LICS'06) , title =

    Mikoaj Boja\'. 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06) , title =. 2006 , pages =. doi:10.1109/LICS.2006.51 , _bib2doi_selected =

    work page doi:10.1109/lics.2006.51 2006

  4. [4]

    Mikolaj Bojanczyk and Anca Muscholl and Thomas Schwentick and Luc Segoufin , title =. J. 2009 , publisher =. doi:10.1145/1516512.1516515 , pages =

    work page doi:10.1145/1516512.1516515 2009

  5. [5]

    Proceedings of the 26th Annual

    Automata with Group Actions , author =. Proceedings of the 26th Annual. 2011 , organization =. doi:10.1109/LICS.2011.48 , publisher =

    work page doi:10.1109/lics.2011.48 2011

  6. [6]

    Data Monoids , booktitle =

    Mikolaj Bojanczyk , editor =. Data Monoids , booktitle =. 2011 , url =. doi:10.4230/LIPIcs.STACS.2011.105 , timestamp =

    work page doi:10.4230/lipics.stacs.2011.105 2011

  7. [7]

    Theory Comput

    Mikolaj Bojanczyk , title =. Theory Comput. Syst. , volume =. 2013 , url =. doi:10.1007/s00224-013-9464-1 , timestamp =

    work page doi:10.1007/s00224-013-9464-1 2013

  8. [8]

    Mikolaj Bojanczyk and Bartek Klin and Slawomir Lasota , title =. Log. Methods Comput. Sci. , volume =. 2014 , timestamp =. doi:10.2168/LMCS-10(3:4)2014 , url =

    work page doi:10.2168/lmcs-10(3:4)2014 2014

  9. [9]

    A draft of a book available at

    Slightly infinite sets , author =. A draft of a book available at. 2019 , _bib2doi_finished =

    work page 2019

  10. [10]

    Bollig and M

    B. Bollig and M. Leucker and T. Noll , title =. Foundations of Software Science and Computation Structures, 5th International Conference, FOSSACS 2002 , editor =. 2002 , publisher =. doi:10.1007/3-540-45931-6_5 , _bib2doi_selected =

    work page doi:10.1007/3-540-45931-6_5 2002

  11. [11]

    Chandra and Dexter C

    Ashok K. Chandra and Dexter Kozen and Larry J. Stockmeyer , title =. J. 1981 , pages =. doi:10.1145/322234.322243 , url =

    work page doi:10.1145/322234.322243 1981

  12. [12]

    Formal Reasoning on Infinite Data Values: An Ongoing Quest , booktitle =

    Taolue Chen and Fu Song and Zhilin Wu , editor =. Formal Reasoning on Infinite Data Values: An Ongoing Quest , booktitle =. 2016 , timestamp =. doi:10.1007/978-3-319-56841-6_6 , url =

    work page doi:10.1007/978-3-319-56841-6_6 2016

  13. [13]

    Edward Y. C. Cheng and Michael Kaminski , title =. Acta Informatica , volume =. 1998 , url =. doi:10.1007/s002360050120 , timestamp =

    work page doi:10.1007/s002360050120 1998

  14. [14]

    Determinisability of register and timed automata , journal =

    Lorenzo Clemente and Slawomir Lasota and Radoslaw Pi. Determinisability of register and timed automata , journal =. 2022 , timestamp =. doi:10.46298/lmcs-18(2:9)2022 , number =

    work page doi:10.46298/lmcs-18(2:9)2022 2022

  15. [15]

    Bounded Languages Over Infinite Alphabets , booktitle =

    Danieli, Yoav and Kaminski, Michael , editor =. Bounded Languages Over Infinite Alphabets , booktitle =. 2025 , publisher =. doi:10.1007/978-3-031-86319-6_15 , url =

    work page doi:10.1007/978-3-031-86319-6_15 2025

  16. [16]

    43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) , pages =

    Danieli, Yoav , title =. 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) , pages =. 2026 , volume =. doi:10.4230/LIPIcs.STACS.2026.29 , annote =

    work page doi:10.4230/lipics.stacs.2026.29 2026

  17. [17]

    St. 21th. 2006 , url =. doi:10.1109/LICS.2006.31 , timestamp =

    work page doi:10.1109/lics.2006.31 2006

  18. [18]

    2009 , url =

    St. 2009 , url =. doi:10.1145/1507244.1507246 , timestamp =

    work page doi:10.1145/1507244.1507246 2009

  19. [19]

    Dickson , title =

    L.E. Dickson , title =. American Journal of Mathematics , volume =. 1913 , pages =

    work page 1913

  20. [20]

    Dubov , title =

    Y. Dubov , title =. 2008 , _bib2doi_finished =

    work page 2008

  21. [21]

    Languages: From Formal to Natural, Essays Dedicated to Nissim Francez on the Occasion of His 65th Birthday , editor =

    Yulia Dubov and Michael Kaminski , title =. Languages: From Formal to Natural, Essays Dedicated to Nissim Francez on the Occasion of His 65th Birthday , editor =. 2009 , pages =. doi:10.1007/978-3-642-01748-3_8 , url =

    work page doi:10.1007/978-3-642-01748-3_8 2009

  22. [22]

    Rational sets in commutative monoids , author =. J. Algebra , volume =. 1969 , _bib2doi_finished =

    work page 1969

  23. [23]

    1974 , url =

    Samuel Eilenberg , title =. 1974 , url =

    work page 1974

  24. [24]

    Proceedings of the 26th Annual

    Diego Figueira and Santiago Figueira and Sylvain Schmitz and Philippe Schnoebelen , year =. Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma , booktitle =. doi:10.1109/LICS.2011.39 , url =

    work page doi:10.1109/lics.2011.39 2011

  25. [25]

    Diego Figueira and Piotr Hofman and Slawomir Lasota , title =. Math. Struct. Comput. Sci. , volume =. 2016 , timestamp =. doi:10.1017/S0960129514000322 , number =

    work page doi:10.1017/s0960129514000322 2016

  26. [26]

    LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022

    Reasoning on Data Words over Numeric Domains , author =. 2022 , timestamp =. doi:10.1145/3531130.3533354 , publisher =

    work page doi:10.1145/3531130.3533354 2022

  27. [27]

    Forward Analysis for WSTS, Part

    Alain Finkel and Jean Goubault. Forward Analysis for WSTS, Part. Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science,. 2009 , url =. doi:10.4230/LIPIcs.STACS.2009.1844 , timestamp =

    work page doi:10.4230/lipics.stacs.2009.1844 2009

  28. [28]

    Forward Analysis for WSTS, Part

    Alain Finkel and Jean Goubault. Forward Analysis for WSTS, Part. Log. Methods Comput. Sci. , volume =. 2012 , url =. doi:10.2168/LMCS-8(3:28)2012 , timestamp =

    work page doi:10.2168/lmcs-8(3:28)2012 2012

  29. [29]

    Nissim Francez and Michael Kaminski , title =. Theor. Comput. Sci. , volume =. 2003 , pages =. doi:10.1016/S0304-3975(03)00246-9 , number =

    work page doi:10.1016/s0304-3975(03)00246-9 2003

  30. [30]

    The yoneda embedding in simplicial type theory

    Florian Frank and Daniel Hausmann and Stefan Milius and Lutz Schr. Alternating Nominal Automata with Name Allocation , booktitle =. 2025 , url =. doi:10.1109/LICS65433.2025.00012 , timestamp =

    work page doi:10.1109/lics65433.2025.00012 2025

  31. [31]

    Daniel Genkin and Michael Kaminski and Liat Peterfreund , title =. Theor. Comput. Sci. , volume =. 2014 , url =. doi:10.1016/j.tcs.2014.01.020 , timestamp =

    work page doi:10.1016/j.tcs.2014.01.020 2014

  32. [32]

    Closure Under Reversal of Languages over Infinite Alphabets , booktitle =

    Daniel Genkin and Michael Kaminski and Liat Peterfreund , editor =. Closure Under Reversal of Languages over Infinite Alphabets , booktitle =. 2018 , timestamp =. doi:10.1007/978-3-319-90530-3_13 , url =

    work page doi:10.1007/978-3-319-90530-3_13 2018

  33. [33]

    Proceedings of the London Mathematical Society , volume =

    Ordering by divisibility in abstract algebras , author =. Proceedings of the London Mathematical Society , volume =. 1952 , publisher =

    work page 1952

  34. [34]

    Parikh's Theorem Made Symbolic , author =. Proc. 2024 , publisher =. doi:10.1145/3632907 , url =

    work page doi:10.1145/3632907 2024

  35. [35]

    Automata, Languages and Programming, 18th International Colloquium, ICALP91, Madrid, Spain, July 8-12, 1991, Proceedings , pages =

    Algorithms for Determining the Smallest Number of Nonterminals (States) Sufficient for Generating (Accepting) a Regular Language , author =. Automata, Languages and Programming, 18th International Colloquium, ICALP91, Madrid, Spain, July 8-12, 1991, Proceedings , pages =. 1991 , organization =. doi:10.1007/3-540-54233-7_170 , publisher =

    work page doi:10.1007/3-540-54233-7_170 1991

  36. [36]

    In: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

    Piotr Hofman and Marta Juzepczuk and Slawomir Lasota and Mohnish Pattathurajan , title =. 36th Annual. 2021 , timestamp =. doi:10.1109/LICS52264.2021.9470626 , url =

    work page doi:10.1109/lics52264.2021.9470626 2021

  37. [37]

    Hopcroft and J.D

    J.E. Hopcroft and J.D. Ullman , title =. 1979 , timestamp =

    work page 1979

  38. [38]

    Jurdzi\'

    M. Jurdzi\'. Alternating automata on data trees and. ACM Transactions Computational Logic , volume =. 2011 , note =. doi:10.1145/1929954.1929956 , _bib2doi_selected =

    work page doi:10.1145/1929954.1929956 2011

  39. [39]

    Kaminski and N

    M. Kaminski and N. Francez , title =. Proceedings of the 31th Annual IEEE Symposium on Foundations of Computer Science , publisher =. 1990 , timestamp =. doi:10.1109/FSCS.1990.89590 , _bib2doi_selected =

    work page doi:10.1109/fscs.1990.89590 1990

  40. [40]

    Michael Kaminski and Nissim Francez , title =. Theor. Comput. Sci. , volume =. 1994 , url =. doi:10.1016/0304-3975(94)90242-9 , timestamp =

    work page doi:10.1016/0304-3975(94)90242-9 1994

  41. [41]

    Computing and Combinatorics, 10th Annual International Conference,

    Michael Kaminski and Tony Tan , title =. Computing and Combinatorics, 10th Annual International Conference,. 2004 , publisher =. doi:10.1007/978-3-540-27798-9_20 , url =

    work page doi:10.1007/978-3-540-27798-9_20 2004

  42. [42]

    Michael Kaminski and Tony Tan , title =. Fundam. Informaticae , year =

    work page

  43. [43]

    Pillars of Computer Science, Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday , editor =

    Michael Kaminski and Tony Tan , title =. Pillars of Computer Science, Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday , editor =. 2008 , timestamp =. doi:10.1007/978-3-540-78127-1_21 , url =

    work page doi:10.1007/978-3-540-78127-1_21 2008

  44. [44]

    Michael Kaminski and Daniel Zeitlin , title =. Int. J. Found. Comput. Sci. , volume =. 2010 , number =. doi:10.1142/S0129054110007532 , url =

    work page doi:10.1142/s0129054110007532 2010

  45. [45]

    2016 , url =

    Ahmet Kara , title =. 2016 , url =

    work page 2016

  46. [46]

    Karp and Raymond E

    Richard M. Karp and Raymond E. Miller , title =. J. Comput. Syst. Sci. , volume =. 1969 , pages =. doi:10.1016/S0022-0000(69)80011-5 , number =

    work page doi:10.1016/s0022-0000(69)80011-5 1969

  47. [47]

    Klin , title =

    B. Klin , title =. 26.03.2014 , howpublished =

    work page 2014

  48. [48]

    Nondeterministic and co-Nondeterministic Implies Deterministic, for Data Languages , booktitle =

    Bartek Klin and Slawomir Lasota and Szymon Torunczyk , editor =. Nondeterministic and co-Nondeterministic Implies Deterministic, for Data Languages , booktitle =. 2021 , timestamp =. doi:10.1007/978-3-030-71995-1_19 , url =

    work page doi:10.1007/978-3-030-71995-1_19 2021

  49. [49]

    D. K\". Sur les correspondences multivoques des ensembles , journal =. 1926 , pages =

    work page 1926

  50. [50]

    Archiv der Mathematik und Physik , volume =

    Edmund Landau , title =. Archiv der Mathematik und Physik , volume =. 1903 , pages =

    work page 1903

  51. [51]

    2008 , url =

    Slawomir Lasota and Igor Walukiewicz , title =. 2008 , url =. doi:10.1145/1342991.1342994 , timestamp =

    work page doi:10.1145/1342991.1342994 2008

  52. [52]

    Parikh Images of Register Automata , booktitle =

    Slawomir Lasota and Mohnish Pattathurajan , editor =. Parikh Images of Register Automata , booktitle =. 2021 , url =. doi:10.4230/LIPIcs.FSTTCS.2021.50 , timestamp =

    work page doi:10.4230/lipics.fsttcs.2021.50 2021

  53. [53]

    Lewis and Christos H

    Harry R. Lewis and Christos H. Papadimitriou , title =. 1981 , url =

    work page 1981

  54. [54]

    M. L\". Hierarchies of Number-Theoretic Functions. Archive for Mathematical Logic , number =. 1971 , _bib2doi_finished =

    work page 1971

  55. [55]

    The Containment Problem for Unambiguous Register Automata , booktitle =

    Antoine Mottet and Karin Quaas , editor =. The Containment Problem for Unambiguous Register Automata , booktitle =. 2019 , timestamp =. doi:10.4230/LIPIcs.STACS.2019.53 , url =

    work page doi:10.4230/lipics.stacs.2019.53 2019

  56. [56]

    Murawski and Steven J

    Andrzej S. Murawski and Steven J. Ramsay and Nikos Tzevelekos , title =. Log. Methods Comput. Sci. , volume =. 2025 , url =. doi:10.46298/lmcs-21(1:13)2025 , timestamp =

    work page doi:10.46298/lmcs-21(1:13)2025 2025

  57. [57]

    Murawski and Steven J

    Andrzej S. Murawski and Steven J. Ramsay and Nikos Tzevelekos , title =. 30th Annual. 2015 , url =. doi:10.1109/LICS.2015.24 , timestamp =

    work page doi:10.1109/lics.2015.24 2015

  58. [58]

    2023 , volume =

    Pumping Lemmas for Languages Expressed by Computational Models with Registers , author =. 2023 , volume =. doi:10.1587/transinf.2022fcp0004 , number =

    work page doi:10.1587/transinf.2022fcp0004 2023

  59. [59]

    Mathematical Proceedings of the Cambridge Philosophical Society , volume =

    On well-quasi-ordering finite trees , author =. Mathematical Proceedings of the Cambridge Philosophical Society , volume =. 1963 , organization =

    work page 1963

  60. [60]

    Mathematical Foundations of Computer Science 2001, 26th International Symposium,

    Frank Neven and Thomas Schwentick and Victor Vianu , title =. Mathematical Foundations of Computer Science 2001, 26th International Symposium,. 2001 , pages =. doi:10.1007/3-540-44683-4_49 , url =

    work page doi:10.1007/3-540-44683-4_49 2001

  61. [61]

    2004 , url =

    Frank Neven and Thomas Schwentick and Victor Vianu , title =. 2004 , url =. doi:10.1145/1013560.1013562 , timestamp =

    work page doi:10.1145/1013560.1013562 2004

  62. [62]

    The Dual of Concatenation , booktitle =

    Alexander Okhotin , editor =. The Dual of Concatenation , booktitle =. 2004 , timestamp =. doi:10.1007/978-3-540-28629-5_54 , url =

    work page doi:10.1007/978-3-540-28629-5_54 2004

  63. [63]

    Alexander Okhotin , title =. Theor. Comput. Sci. , volume =. 2005 , timestamp =. doi:10.1016/j.tcs.2005.07.019 , url =

    work page doi:10.1016/j.tcs.2005.07.019 2005

  64. [64]

    Rohit Parikh , title =. J. 1966 , pages =. doi:10.1145/321356.321364 , number =

    work page doi:10.1145/321356.321364 1966

  65. [65]

    2013 , publisher =

    Nominal sets: Names and symmetry in computer science , author =. 2013 , publisher =

    work page 2013

  66. [66]

    Post , title =

    E.L. Post , title =. Bulletin of the American Mathematical Society , volume =. 1946 , pages =

    work page 1946

  67. [67]

    Rabin and Dana S

    Michael O. Rabin and Dana S. Scott , title =. 1959 , url =. doi:10.1147/rd.32.0114 , timestamp =

    work page doi:10.1147/rd.32.0114 1959

  68. [68]

    International Colloquium Universal Machines and Computations, MCU'98, Metz, France, March 23-27, 1998, Proceedingsi, Volume

    Hiroshi Sakamoto and Daisuke Ikeda , title =. International Colloquium Universal Machines and Computations, MCU'98, Metz, France, March 23-27, 1998, Proceedingsi, Volume. 1998 , timestamp =

    work page 1998

  69. [69]

    Hiroshi Sakamoto and Daisuke Ikeda , title =. Theor. Comput. Sci. , volume =. 2000 , pages =. doi:10.1016/S0304-3975(99)00105-X , number =

    work page doi:10.1016/s0304-3975(99)00105-x 2000

  70. [70]

    Mathematical Foundations of Computer Science 2010, 35th International Symposium,

    Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets , author =. Mathematical Foundations of Computer Science 2010, 35th International Symposium,. 2010 , url =. doi:10.1007/978-3-642-15155-2_54 , publisher =

    work page doi:10.1007/978-3-642-15155-2_54 2010

  71. [71]

    Automata and Logics for Words and Trees over an Infinite Alphabet , booktitle =

    Luc Segoufin , editor =. Automata and Logics for Words and Trees over an Infinite Alphabet , booktitle =. 2006 , timestamp =. doi:10.1007/11874683_3 , url =

    work page doi:10.1007/11874683_3 2006

  72. [72]

    Yael Shemesh and Nissim Francez , title =. Inf. Comput. , volume =. 1994 , pages =. doi:10.1006/inco.1994.1085 , number =

    work page doi:10.1006/inco.1994.1085 1994

  73. [73]

    Tal , title =

    A. Tal , title =. 1999 , _bib2doi_finished =

    work page 1999

  74. [74]

    Mathematical Foundations of Computer Science 2009, 34th International Symposium,

    Tony Tan , title =. Mathematical Foundations of Computer Science 2009, 34th International Symposium,. 2009 , publisher =. doi:10.1007/978-3-642-03816-7_60 , url =

    work page doi:10.1007/978-3-642-03816-7_60 2009

  75. [75]

    Tony Tan , title =. J. Comput. Syst. Sci. , volume =. 2010 , pages =. doi:10.1016/j.jcss.2010.03.004 , number =

    work page doi:10.1016/j.jcss.2010.03.004 2010

  76. [76]

    Zeitlin , title =

    D. Zeitlin , title =. 2006 , _bib2doi_finished =

    work page 2006