A Robust Class of Linear Recurrence Sequences

Corentin Barloy; Filip Mazowiecki; Nathana\"el Fijalkow; Nathan Lhote

REVIEW 3 major objections 5 minor 19 references

A Robust Class of Linear Recurrence Sequences

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper introduces poly-rational sequences and proves they coincide with polynomially ambiguous weighted automata, copyless cost-register automata, and linear recurrence sequences whose eigenvalues are roots of rational numbers.

desk verdict A genuinely new five-way equivalence for poly-rational sequences, but the proof of Lemma 9 contains a false factorization claim; the gap is repairable and the paper deserves a serious referee. read the letter →

arxiv 1908.03890 v1 pith:PEPREY5V submitted 2019-08-11 cs.FL

Corentin Barloy , Nathanaël Fijalkow , Nathan Lhote , Filip Mazowiecki This is my paper · ORCID

classification cs.FL MSC 11B3768Q45

keywords poly-rationalsequenceslinearrecurrenceweightedautomatacost-registerformalseriespolynomialambiguitycopylesssubstitutionseigenvalues

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper carves out a tractable subclass of linear recurrence sequences and shows that the same subclass emerges from four very different definitions. The class, called poly-rational sequences, is the smallest family containing arithmetic and geometric sequences and closed under sum, componentwise product, shift, and shuffle. The authors prove it equals the sequences recognised by polynomially ambiguous weighted automata, by copyless cost-register automata, and by linear recurrences whose eigenvalues are roots of rational numbers—equivalently, formal series $P/Q$ whose denominator roots are roots of rationals. If the paper is right, this gives a clean boundary inside linear recurrences: the Fibonacci sequence, whose eigenvalues involve $\sqrt{5}$, falls outside, and decidability and hardness results for one presentation transfer to all the others.

What carries the argument

The central object is the class $\mathrm{PolyRat} = \mathrm{Rat}[\mathrm{Arith}\cup\mathrm{Geo}, +, \times, \mathrm{shift}, \mathrm{shuffle}]$, the smallest family containing arithmetic and geometric sequences and closed under sum, Hadamard product, shift, and shuffle. The argument is carried by two decompositions: Lemma 7 splits any polynomially ambiguous weighted automaton into a union of chained loops—paths whose states each belong to at most one loop—and Lemma 8 computes the formal series of a chained loop as sums and Cauchy products of $\alpha/(1-\lambda x^\ell)$. For copyless cost-register automata, the load-bearing mechanism is a normal-form theorem for copyless substitutions, which turns every register update into either a stabilising constant or a one-dimensional affine recurrence $u(n+1)=a\,u(n)+b$, and both forms are poly-rational. These mechanisms convert each machine model into an explicit rational formal series, and back again.

What would settle it

Factor the reduced formal series of any polynomially ambiguous weighted automaton: the paper predicts every irreducible factor of the denominator has the form $1-\lambda x^\ell$. One automaton whose denominator contains an irreducible factor such as $x^2-x-1$—the Fibonacci characteristic polynomial—would refute Theorem 15; the mirror test is a copyless cost-register automaton whose eigenvalues include a number like $(1+\sqrt{5})/2$.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 15: poly-rational sequences are exactly the linear recurrence sequences whose eigenvalues are roots of rational numbers, equivalently those whose formal series are $P/Q$ with $P,Q$ rational polynomials and all roots of $Q$ roots of rational numbers. Together with Theorems 6 and 13 this yields a five-way effective equivalence among poly-rational expressions, polynomially ambiguous weighted automata, copyless cost-register automata, rational formal series of that restricted kind, and eigenvalue-restricted linear recurrences. The proof route is explicit: a polynomially ambiguous weighted automaton decomposes into chained loops, each contributing a series of the form $\alpha/(1-\lambda x^\ell)$, and sums and Cauchy products of these are precisely the rational series whose denominator roots are roots of rational numbers; conversely, each such series is built inside PolyRat by Lemma 10. A notable consequence is that the Fibonacci sequence is not poly-rational, since its eigenvalues $(1\pm\sqrt{5})/2$ are not roots of rational numbers.

Load-bearing premise

The inclusion CCRA ⊆ PolyRat relies on the cited theorem that every copyless cost-register automaton can be put into normal form, with registers updated in a fixed order and no register copied; if that structural theorem failed, the equivalence would lose one of its five directions.

Editorial extensions

If this is right

The Fibonacci sequence is not poly-rational, since its eigenvalues are not roots of rational numbers; hence it cannot be recognised by a polynomially ambiguous weighted automaton or a copyless cost-register automaton.
The Skolem problem—whether a given sequence hits zero—is decidable and NP-hard for poly-rational sequences, transferring the known lower bound for eigenvalues that are roots of unity to all four equivalent presentations.
The ambiguity hierarchy of weighted automata is strict: deterministic, finitely ambiguous, polynomially ambiguous, and unrestricted weighted automata form a strictly increasing chain, with explicit separating sequences for each strict inclusion.
PolyRat is closed under Cauchy product even though that closure was not immediate from its definition; closure follows from the equivalence with rational formal series.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

One testable extension is to grade the class by the degree of the radical: eigenvalues that are roots of rationals of bounded degree might yield a hierarchy of tractable subclasses, with roots of unity at the bottom.
If the one-letter-alphabet restriction is essential, as the authors conjecture, the clean boundary identified here is a property of unary sequences rather than of general weighted automata.
The chained-loop normal form suggests a concrete algorithm for the Skolem problem on poly-rational sequences: reduce to checking whether a finite sum of terms $c\,\lambda^n n^k$ with $\lambda$ a root of a rational ever vanishes, which is a Diophantine condition that may be decidable by elementary arguments.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know about arXiv:1908.03890. The paper defines poly-rational sequences and proves a five-way equivalence: the same class is captured by polynomially ambiguous weighted automata, copyless cost-register automata, rational formal series whose denominator roots are roots of rational numbers, and LRS whose eigenvalues are roots of rational numbers. The genuinely new piece is the equality CCRA = PolyWA; prior work only had CCRA strictly inside all weighted automata.

What's good: the class is natural and the four characterizations are proved by elementary constructions. The paper is clearly written and the definitions are memorable. Lemma 14's induction for copyless substitutions is the nicest part of the paper. If the main theorem is correct, it gives a useful algorithmic fragment: the Skolem problem is decidable for the class, with known NP-hardness.

The soft spots are in the proofs, not the statements. Lemma 9's proof asserts that any polynomial whose roots are roots of rational numbers is a product of mutually prime polynomials (1−λx^ℓ)^k. That's false. Take Q(x)=1+2x^2+4x^4: it's irreducible, every root α satisfies α^6=1/8, but Q cannot be factored into such polynomials over Q. The lemma's conclusion is still true—each irreducible factor of Q divides some 1−λx^m, so partial fractions give the desired sum—but the proof needs a different argument. Since Lemma 9 is used in both directions of Theorem 15 and in PolyWA⊆PolyRat, the authors must fix this.

Smaller issues: Lemma 10's displayed expansion has the wrong binomial coefficient (C(n+k−1,k) should be C(n+k−1,k−1)); Lemma 7's chained-loop decomposition is sketched, and the claim that a state is in at most one loop needs a fuller argument; Lemma 12's strictness examples are explicitly omitted. The normal form for CCRA is imported from the authors' own JCSS paper; that's legitimate, but the current paper depends on it.

My read: the central claim is almost certainly correct and repairable. The paper deserves a serious refereeing cycle, not a desk reject. I'd want the Lemma 9 proof rewritten and the smaller gaps patched before publication, but this is a real contribution to the automata/LRS literature.

Referee Report

3 major / 5 minor

Summary. The paper introduces poly-rational sequences (PolyRat), defined as the smallest class containing arithmetic and geometric sequences and closed under sum, Hadamard product, shift, and shuffle. The central claim is that PolyRat is robust: it coincides with the classes of sequences recognised by polynomially ambiguous weighted automata (PolyWA), copyless cost-register automata (CCRA), rational formal series P/Q with Q having only roots that are roots of rational numbers, and linear recurrence sequences whose eigenvalues are roots of rational numbers. The authors also use this equivalence to show that the Fibonacci sequence is not in PolyRat and to place the Skolem problem for the class in NP-hard and decidable.

Significance. If the main theorem holds, this is a clean and useful robustness result: it connects four independently motivated notions—expression classes, ambiguity-bounded automata, register automata with a copyless restriction, and an algebraic condition on eigenvalues. The paper gives constructive, elementary translations between the characterisations and derives a concrete separation (Fibonacci is excluded), which strengthens the known separation of CCRA from LCRA. The paper's strengths are the breadth and simplicity of the proposed characterisations, and the fact that several equivalences are proved by explicit constructions rather than by invoking heavy machinery. However, the current proof contains a false step in a key lemma, and another lemma relies on an unstated linearity assumption; these must be repaired before the main theorem can be considered established.

major comments (3)

[Section 5, Lemma 9] The proof of Lemma 9 contains a false assertion: it claims that any polynomial whose roots are roots of rational numbers can be written over Q as a product of mutually prime polynomials of the form (1 - lambda x^ell)^k. This is not true. The polynomial Q(x) = 1 + 2x^2 + 4x^4 is irreducible over Q, its roots alpha satisfy alpha^6 = 1/8, yet Q cannot be proportional to any (1 - lambda x^ell)^k: a binomial factor has at most two nonzero terms, and direct comparison for ell = 2, k = 1, 2 and ell = 4 fails. Since Lemma 9 is used in both directions of Theorem 15 and in the proof of PolyWA subset PolyRat in Section 3, the central equivalence is not proved as written. The statement of Lemma 9 may be salvageable by a different argument, namely that every irreducible factor q of Q divides some x^m - c with c in Q, so that P/Q can be put in the required partial-fraction form; but the proof in the manuscript must be replaced by a correct argument.
[Section 4, proof of Lemma 14] Lemma 14 is stated for every copyless substitution in normal form, but its proof assumes that sigma(x) is a linear expression, writing sigma(x) as sum_i a_i x_i. The definition of CCRA given in Section 4 allows products of registers in substitutions. The paper cites [12] for the fact that CCRA is a subclass of linear CRA, but it does not show that the linearisation preserves copylessness and normal form, which are essential hypotheses of Lemma 14. Without such a preservation result, the proof of CCRA subset PolyRat only covers linear copyless substitutions, and Theorem 13 is not fully supported. Please either prove the needed reduction to linear copyless normal form, or extend the argument of Lemma 14 to polynomial copyless substitutions.
[Section 3, Lemma 7] The decomposition of polynomially ambiguous automata into a union of chained loops is load-bearing for Theorem 6 and for the formal-series characterisation, but the proof is only sketched. In particular, the claim that a state contained in two loops induces exponential ambiguity is stated without proof, and the asserted bijection between runs of A and runs of the union of all induced chained loops is not demonstrated. Please give a formal graph-theoretic proof, making explicit how runs are decomposed into a simple path with repetitions of unique simple loops, and how the weights of the original run match the value in the union of chained loops.

minor comments (5)

[Section 3, Lemma 10] The displayed expansion in the proof of Lemma 10 uses the binomial coefficient binom(n+k-1, k), but the coefficient of x^n in (1-x)^{-k} is binom(n+k-1, k-1). The subsequent argument only needs that the coefficient sequence is polynomial in n, so the error is not fatal, but the formula should be corrected.
[Section 4, paragraph on normal form] The paper imports [14, Proposition 1] (existence of an equivalent CCRA in normal form) as a black box. Since this result is central to the CCRA subset PolyRat direction and comes from the authors' own prior work, please state the theorem precisely and, ideally, include a proof or a detailed reference statement in an appendix.
[Section 3, Lemma 12] The proofs of the first three items of Lemma 12 are omitted. These items establish the strict inclusions in the ambiguity hierarchy, which is a stated application of the paper; please include at least sketches of these proofs.
[Section 3, proof of Theorem 6, shift construction] In the shift construction for a = 0, the text should state explicitly that the new initial state q0 is not final and that the original initial weights are moved to the new outgoing transitions; as written, the value of the length-zero run is left implicit.
[Theorem 2] The phrase 'effectively equivalent' is used without a precise definition. Please clarify that the reductions are computable, and state whether any complexity bound is intended.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the equivalences are proved by explicit automata and register-machine constructions; the only self-cited normal-form theorem is independent, parameter-free support.

full rationale

I walked the derivation chain. PolyRat is defined as Rat[Arith∪Geo,+,×,shift,shuffle], an independent syntactic class, and the claimed characterisations are proved by explicit constructions: Theorem 6 gives both inclusions for PolyWA via automata closures and chained-loop decompositions (Lemmas 7–10); Theorem 13 handles CCRA by direct register constructions and the normal-form induction in Lemma 14; Theorem 15 uses classical LRS formal-series facts plus Lemma 10. No fitted parameter is renamed as a prediction, and none of the constructions assume the theorem being proved. The only load-bearing citation overlapping with the authors is [14, Proposition 1] (existence of an equivalent CCRA in normal form), used to justify the induction in Lemma 14; that theorem is a structural statement about copyless cost-register automata, does not mention PolyRat or polynomial ambiguity, and is published in JCSS, so it is independent support rather than a circular premise. The paper also cites [12] for CCRA⊆LCRA, again an external structural result. I also note a correctness concern, not a circularity concern: the proof of Lemma 9 as written asserts a polynomial-factorisation claim that is not established as written; if that gap cannot be repaired, the proof of Theorem 15 is incomplete, but incompleteness is not equivalence-by-construction. Under the circularity standard of quote-and-reduce, I find no circular step.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted constants and no new postulated objects. Its dependency deck is two results about cost-register automata from the same research line (normal form and expressivity), plus standard rational-series algebra. These are structural theorems, not benchmark fitting, so they are listed as axioms rather than circular assumptions.

assumptions (4)

domain assumption Every CCRA has an equivalent CCRA in normal form (order on registers with σ(xi) using only xj ≥ xi).
Section 4, proof of Theorem 13, invoked as [14, Proposition 1]; the entire CCRA ⊆ PolyRat direction depends on it.
domain assumption Linear cost-register automata recognize exactly weighted automata sequences, and copyless CRAs are a subclass.
Used in Section 4 and cited from [3] and [12].
standard math The formal series of a linear recurrence sequence is P/Q for rational polynomials P,Q.
Lemma 16, cited from [8]; classical generating-function theory.
standard math Q[x] is a Euclidean ring, so rational formal series with roots of Q being roots of rationals decompose into sums of R/(1-λx^ℓ)^k.
Lemma 9; standard algebra.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Robust Class of Linear Recurrence Sequences." pith.science (2026). https://pith.science/paper/PEPREY5V

@misc{pith2026190803890,
  author       = {Pith},
  title        = {Pith review of: A Robust Class of Linear Recurrence Sequences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PEPREY5V}},
  note         = {Machine review of arXiv:1908.03890}
}

read the original abstract

We introduce a subclass of linear recurrence sequences which we call poly-rational sequences because they are denoted by rational expressions closed under sum and product. We show that this class is robust by giving several characterisations: polynomially ambiguous weighted automata, copyless cost-register automata, rational formal series, and linear recurrence sequences whose eigenvalues are roots of rational numbers.

Figures

Figures reproduced from arXiv: 1908.03890 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 10 canonical work pages

[12]

Maximal partition logic: Towards a logical characterization of copyless cost register automata

Filip Mazowiecki and Cristian Riveros. Maximal partition logic: Towards a logical characterization of copyless cost register automata. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015, September 7-10, 2015, Berlin, Germany , pages 144--159, 2015. URL: https://doi.org/10.4230/LIPIcs.CSL.2015.144, http://dx.doi.org/10.4230/LIPIcs.CSL.2015...

work page doi:10.4230/lipics.csl.2015.144 2015
[1]

Akshay, Nikhil Balaji, and Nikhil Vyas

S. Akshay, Nikhil Balaji, and Nikhil Vyas. Complexity of restricted variants of skolem and related problems. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark , pages 78:1--78:14, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.78, http://dx.doi.org/10.4230/LIPIcs.MFCS.201...

doi:10.4230/lipics.mfcs.2017.78 2017
[2]

P \' e rez

Shaull Almagor, Micha \" e l Cadilhac, Filip Mazowiecki, and Guillermo A. P \' e rez. Weak cost register automata are still powerful. In Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings , pages 83--95, 2018. URL: https://doi.org/10.1007/978-3-319-98654-8\_7, http://dx.doi.org/10.10...

work page doi:10.1007/978-3-319-98654-8 2018
[3]

Deshmukh, Mukund Raghothaman, and Yifei Yuan

Rajeev Alur, Loris D'Antoni, Jyotirmoy V. Deshmukh, Mukund Raghothaman, and Yifei Yuan. Regular functions and cost register automata. In 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013 , pages 13--22, 2013. URL: https://doi.org/10.1109/LICS.2013.65, http://dx.doi.org/10.1109/LICS.2013.65 doi:1...

doi:10.1109/lics.2013.65 2013
[4]

Algebraic generating functions in enumerative combinatorics and context-free languages

Mireille Bousquet - M \' e lou. Algebraic generating functions in enumerative combinatorics and context-free languages. In STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings , pages 18--35, 2005. URL: https://doi.org/10.1007/978-3-540-31856-9\_2, http://dx.doi.org/10.1007/978...

doi:10.1007/978-3-540-31856-9 2005
[5]

Weighted automata and weighted logics

Manfred Droste and Paul Gastin. Weighted automata and weighted logics. Theoretical Computer Science , 380(1-2):69--86, 2007. URL: https://doi.org/10.1016/j.tcs.2007.02.055, http://dx.doi.org/10.1016/j.tcs.2007.02.055 doi:10.1016/j.tcs.2007.02.055

work page doi:10.1016/j.tcs.2007.02.055 2007
[6]

Handbook of Weighted Automata

Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata . Springer, 1st edition, 2009

2009
[7]

Probabilistic automata of bounded ambiguity

Nathana \" e l Fijalkow, Cristian Riveros, and James Worrell. Probabilistic automata of bounded ambiguity. In Roland Meyer and Uwe Nestmann, editors, 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany , volume 85 of LIPIcs , pages 19:1--19:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL...

work page doi:10.4230/lipics.concur.2017.19 2017

Show all 19 references

[8]

Graham, Donald E

Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete mathematics - a foundation for computer science (2. ed.) . Addison-Wesley, 1994

1994
[9]

Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata

Daniel Kirsten and Sylvain Lombardy. Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings , pages 589--60...

2009
[10]

Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton

Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoretical Computer Science , 327(3):349--373, 2004. URL: https://doi.org/10.1016/j.tcs.2004.02.049, http://dx.doi.org/10...

2004 doi
[11]

Quantitative monadic second-order logic

Stephan Kreutzer and Cristian Riveros. Quantitative monadic second-order logic. In 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013 , pages 113--122, 2013. URL: https://doi.org/10.1109/LICS.2013.16, http://dx.doi.or...

2013 doi
[13]

Pumping lemmas for weighted automata

Filip Mazowiecki and Cristian Riveros. Pumping lemmas for weighted automata. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France , pages 50:1--50:14, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.50, http:...

2018 doi
[14]

Copyless cost-register automata: Structure, expressiveness, and closure properties

Filip Mazowiecki and Cristian Riveros. Copyless cost-register automata: Structure, expressiveness, and closure properties. Journal of Computer and System Sciences , 100:1--29, 2019. URL: https://doi.org/10.1016/j.jcss.2018.07.002, http://dx.doi.org/10.1016/j.jcss.2018.07.002 d...

2019 doi
[16]

Ultimate positivity is decidable for simple linear recurrence sequences

Jo \" e l Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II , pages 330--341, 2014...

2014 doi
[17]

On linear recurrence sequences and loop termination

Jo \" e l Ouaknine and James Worrell. On linear recurrence sequences and loop termination. SIGLOG News , 2(2):4--13, 2015. URL: http://doi.acm.org/10.1145/2766189.2766191, http://dx.doi.org/10.1145/2766189.2766191 doi:10.1145/2766189.2766191

2015
[18]

On the termination of linear and affine programs over the integers

Rachid Rebiha, Arnaldo Vieira Moura, and Nadir Matringe. On the termination of linear and affine programs over the integers. CoRR , abs/1409.4230, 2014. URL: http://arxiv.org/abs/1409.4230, http://arxiv.org/abs/1409.4230 arXiv:1409.4230

2014 arXiv
[19]

On the definition of a family of automata

Marcel Paul Sch \" u tzenberger. On the definition of a family of automata. Information and Control , 4(2-3):245--270, 1961. URL: https://doi.org/10.1016/S0019-9958(61)80020-X, http://dx.doi.org/10.1016/S0019-9958(61)80020-X doi:10.1016/S0019-9958(61)80020-X

1961 doi
[20]

Structure and randomness: pages from year one of a mathematical blog

Terence Tao. Structure and randomness: pages from year one of a mathematical blog . American Mathematical Society Providence, RI, 2008

2008

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [12]

Maximal partition logic: Towards a logical characterization of copyless cost register automata

Filip Mazowiecki and Cristian Riveros. Maximal partition logic: Towards a logical characterization of copyless cost register automata. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015, September 7-10, 2015, Berlin, Germany , pages 144--159, 2015. URL: https://doi.org/10.4230/LIPIcs.CSL.2015.144, http://dx.doi.org/10.4230/LIPIcs.CSL.2015...

work page doi:10.4230/lipics.csl.2015.144 2015

[2] [1]

Akshay, Nikhil Balaji, and Nikhil Vyas

S. Akshay, Nikhil Balaji, and Nikhil Vyas. Complexity of restricted variants of skolem and related problems. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark , pages 78:1--78:14, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.78, http://dx.doi.org/10.4230/LIPIcs.MFCS.201...

doi:10.4230/lipics.mfcs.2017.78 2017

[3] [2]

P \' e rez

Shaull Almagor, Micha \" e l Cadilhac, Filip Mazowiecki, and Guillermo A. P \' e rez. Weak cost register automata are still powerful. In Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings , pages 83--95, 2018. URL: https://doi.org/10.1007/978-3-319-98654-8\_7, http://dx.doi.org/10.10...

work page doi:10.1007/978-3-319-98654-8 2018

[4] [3]

Deshmukh, Mukund Raghothaman, and Yifei Yuan

Rajeev Alur, Loris D'Antoni, Jyotirmoy V. Deshmukh, Mukund Raghothaman, and Yifei Yuan. Regular functions and cost register automata. In 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013 , pages 13--22, 2013. URL: https://doi.org/10.1109/LICS.2013.65, http://dx.doi.org/10.1109/LICS.2013.65 doi:1...

doi:10.1109/lics.2013.65 2013

[5] [4]

Algebraic generating functions in enumerative combinatorics and context-free languages

Mireille Bousquet - M \' e lou. Algebraic generating functions in enumerative combinatorics and context-free languages. In STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings , pages 18--35, 2005. URL: https://doi.org/10.1007/978-3-540-31856-9\_2, http://dx.doi.org/10.1007/978...

doi:10.1007/978-3-540-31856-9 2005

[6] [5]

Weighted automata and weighted logics

Manfred Droste and Paul Gastin. Weighted automata and weighted logics. Theoretical Computer Science , 380(1-2):69--86, 2007. URL: https://doi.org/10.1016/j.tcs.2007.02.055, http://dx.doi.org/10.1016/j.tcs.2007.02.055 doi:10.1016/j.tcs.2007.02.055

work page doi:10.1016/j.tcs.2007.02.055 2007

[7] [6]

Handbook of Weighted Automata

Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata . Springer, 1st edition, 2009

2009

[8] [7]

Probabilistic automata of bounded ambiguity

Nathana \" e l Fijalkow, Cristian Riveros, and James Worrell. Probabilistic automata of bounded ambiguity. In Roland Meyer and Uwe Nestmann, editors, 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany , volume 85 of LIPIcs , pages 19:1--19:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL...

work page doi:10.4230/lipics.concur.2017.19 2017