Pumping lemmas for weighted automata

DOI10.4230/LIPICS.STACS.2018.50zbMATH Open1487.68151MaRDI QIDQ3304149FDOQ3304149

Authors: Filip Mazowiecki, Cristian Riveros 

Publication date: 5 August 2020

Recommendations

• scientific article; zbMATH DE number 7407779
• scientific article; zbMATH DE number 871243
• On computational power of weighted finite automata
• On deterministic weighted automata
• Which finitely ambiguous automata recognize finitely sequential functions? (extended abstract)

zbMATH Keywords

weighted automatapumping lemmasregular functions over words

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Handbook of weighted automata
• An application of games to the completeness problem for formalized theories
• On the definition of a family of automata
• A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
• Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
• On the positivity problem for simple linear recurrence sequences
• What's decidable about weighted automata?
• Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata
• Weighted automata and weighted logics
• Temporal specifications with accumulative values
• Finite-valued distance automata
• The equality problem for rational series with multiplicities in the tropical semiring is undecidable
• Ultimate positivity is decidable for simple linear recurrence sequences
• Regular functions and cost register automata (invited paper)
• Copyless cost-register automata: structure, expressiveness, and closure properties
• Quantitative Monadic Second-Order Logic
• Decision problems for additive regular functions
• Cost functions definable by min/max automata
• A generalised twinning property for minimisation of cost register automata
• Descriptive complexity for counting complexity classes

Cited In (12)

• Title not available (Why is that?)
• Title not available (Why is that?)
• A robust class of linear recurrence sequences
• Finite sequentiality of finitely ambiguous max-plus tree automata
• A Chomsky-Schützenberger Theorem for Weighted Automata with Storage
• Title not available (Why is that?)
• Finite sequentiality of unambiguous max-plus tree automata
• An ambiguity hierarchy of weighted context-free grammars
• Ambiguity Hierarchies for Weighted Tree Automata
• The boundedness and zero isolation problems for weighted automata over nonnegative rationals
• An ambiguity hierarchy of weighted context-free grammars
• Ambiguity hierarchies for weighted tree automata

This page was built for publication: Pumping lemmas for weighted automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304149)