×

Pumping lemmas for weighted automata. (English) Zbl 1487.68143

Summary: We present pumping lemmas for five classes of functions definable by fragments of weighted automata over the min-plus semiring, the max-plus semiring and the semiring of natural numbers. As a corollary we show that the hierarchy of functions definable by unambiguous, finitely-ambiguous, polynomially-ambiguous weighted automata, and the full class of weighted automata is strict for the min-plus and max-plus semirings.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] Shaull Almagor, Udi Boker, and Orna Kupferman. What’s decidable about weighted automata? InATVA, pages 482-491, 2011. · Zbl 1348.68089
[2] Shaull Almagor, Michaël Cadilhac, Filip Mazowiecki, and Guillermo A. Pérez. Weak cost register automata are still powerful. InDevelopments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings, pages 83-95, 2018. · Zbl 1458.68079
[3] Rajeev Alur and Mukund Raghothaman. Decision problems for additive regular functions. In Automata, Languages, and Programming, pages 37-48. Springer, 2013. · Zbl 1335.68113
[4] Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, and Filip Mazowiecki. A robust class of linear recurrence sequences. In28th EACSL Annual Conference on Computer Science Logic, CSL
[5] Karel Culik II and Jarkko Kari. Image compression using weighted finite automata. InMathematical Foundations of Computer Science 1993, pages 392-402. Springer, 1993.
[6] Thomas Colcombet, Denis Kuperberg, Amaldev Manuel, and Szymon Toruńczyk. Cost functions definable by min/max automata. In33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 29:1-29:13, 2016. · Zbl 1388.68191
[7] Manfred Droste and Paul Gastin. Weighted automata and weighted logics.Theor. Comput. Sci., 380(1-2):69-86, 2007. · Zbl 1118.68076
[8] Manfred Droste and Paul Gastin. Aperiodic weighted automata and weighted first-order logic. In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, pages 76:1-76:15, 2019. · Zbl 1084.03036
[9] Manfred Droste, Werner Kuich, and Heiko Vogler.Handbook of Weighted Automata. Springer, 1st edition, 2009. · Zbl 1200.68001
[10] Laure Daviaud, Pierre-Alain Reynier, and Jean-Marc Talbot. A generalised twinning property for minimisation of cost register automata. InLICS, 2016. · Zbl 1401.68160
[11] Andrzej Ehrenfeucht. An application of games to the completeness problem for formalized theories. Fund. Math, 49(129-141):13, 1961. · Zbl 0096.24303
[12] Ronald Fraïssé. Sur quelques classifications des systèmes de relations.Université d’Alger, Publications Scientifiques, Série A, 1:35-182, 1984. · Zbl 0068.24302
[13] John E. Hopcroft and Jeffrey D. Ullman.Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. · Zbl 0426.68001
[14] Daniel Kirsten. A Burnside approach to the termination of Mohri’s algorithm for polynomially ambiguous min-plus-automata.ITA, 42(3):553-581, 2008. · Zbl 1155.68042
[15] Daniel Kirsten and Sylvain Lombardy. Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata. InSTACS, pages 589-600, 2009. · Zbl 1236.68172
[16] Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton.Theor. Comput. Sci., 327(3):349- 373, 2004. · Zbl 1071.68035
[17] Stephan Kreutzer and Cristian Riveros. Quantitative monadic second-order logic. InLICS, pages 113-122. IEEE Computer Society, 2013. · Zbl 1366.03216
[18] Daniel Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. InICALP, pages 101-112, 1992. · Zbl 1425.68213
[19] Leonid Libkin.Elements of finite model theory. Springer Science & Business Media, 2013. · Zbl 1060.03002
[20] Mehryar Mohri. Finite-state transducers in language and speech processing.Computational Linguistics, 23(2):269-311, 1997.
[21] Filip Mazowiecki and Cristian Riveros. Maximal partition logic: towards a logical characterization of copyless cost register automata. InCSL, 2015. · Zbl 1434.03103
[22] Filip Mazowiecki and Cristian Riveros. Pumping lemmas for weighted automata. In35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, · Zbl 1487.68151
[23] Filip Mazowiecki and Cristian Riveros. Copyless cost-register automata: Structure, expressiveness, and closure properties.J. Comput. Syst. Sci., 100:1-29, 2019. · Zbl 1421.68050
[24] Joël Ouaknine and James Worrell. On the positivity problem for simple linear recurrence sequences,. InICALP, pages 318-329, 2014. · Zbl 1410.11134
[25] Joël Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. InICALP, pages 330-341, 2014. · Zbl 1410.11135
[26] Christos H. Papadimitriou.Computational complexity. Addison-Wesley, 1993. · Zbl 0833.68049
[27] Jean-Éric Pin. Mathematical foundations of automata theory.Lecture notes LIAFA, Université Paris, 7, 2010.
[28] Jacques Sakarovitch.Elements of Automata Theory. Cambridge University Press, 2009. · Zbl 1188.68177
[29] M.-P. Schützenberger. On the definition of a family of automata.Information and Control, 4:245-270, 1961. · Zbl 0104.00702
[30] M.-P. Schützenberger. On finite monoids having only trivial subgroups.Information and Control, 8:190-194, 1965. · Zbl 0131.02001
[31] Andreas Weber. Finite-valued distance automata.Theor. Comput. Sci., 134(1):225-251, 1994. · Zbl 0938.68709
[32] Andreas Weber and Helmut Seidl. On the degree of ambiguity of finite automata.Theoretical Computer Science, 88(2):325-349, 1991. · Zbl 0738.68059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.