PUMPING LEMMAS FOR WEIGHTED AUTOMATA

Simple item page
dc.contributor.authorChattopadhyay, Agnishom
dc.contributor.authorMazowiecki, Filip
dc.contributor.authorMuscholl, Anca
dc.contributor.authorRiveros, Cristian
dc.date.accessioned2025-01-20T22:12:51Z
dc.date.available2025-01-20T22:12:51Z
dc.date.issued2021
dc.description.abstractWe 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.
dc.fuente.origenWOS
dc.identifier.doi10.46298/LMCS-17(3:7)2021
dc.identifier.issn1860-5974
dc.identifier.urihttps://doi.org/10.46298/LMCS-17(3:7)2021
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/94436
dc.identifier.wosidWOS:000679383000001
dc.issue.numero3
dc.language.isoen
dc.revistaLogical methods in computer science
dc.rightsacceso restringido
dc.titlePUMPING LEMMAS FOR WEIGHTED AUTOMATA
dc.typeartículo
dc.volumen17
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas