Agnishom Chattopadhyay ; Filip Mazowiecki ; Anca Muscholl ; Cristian Riveros - Pumping lemmas for weighted automata

lmcs:6039 - Logical Methods in Computer Science, July 21, 2021, Volume 17, Issue 3 - https://doi.org/10.46298/lmcs-17(3:7)2021
Pumping lemmas for weighted automata

Authors: Agnishom Chattopadhyay ; Filip Mazowiecki ; Anca Muscholl ; Cristian Riveros

    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.

    https://doi.org/10.46298/lmcs-17(3:7)2021
    Source : oai:arXiv.org:2001.06272
    Volume: Volume 17, Issue 3
    Published on: July 21, 2021
    Accepted on: May 29, 2021
    Submitted on: January 20, 2020
    Keywords: Computer Science - Logic in Computer Science
    Licence: Attribution 4.0 International (CC BY 4.0)
    Fundings :
      Source : OpenAIRE Graph
    • Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007
    • Counter Automata: Verification and Synthesis; Funder: UK Research and Innovation; Code: EP/M012298/1
    • Counter Automata: Verification and Synthesis; Funder: UK Research and Innovation; Code: EP/M011801/1

    2 Documents citing this article

    Export

    BibTeX TEI DC OpenAIRE Crossref DOAJ zbJATS JSON

    Share

    Consultation statistics

    This page has been seen 324 times.
    This article's PDF has been downloaded 202 times.