2026-07-23T05:31:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5730 2024-03-06T10:36:56Z ddc:004 open_access

Cost Functions Definable by Min/Max Automata Colcombet, Thomas Kuperberg, Denis Manuel, Amaldev Torunczyk, Szymon distance automata B-automata regular cost functions stabilisation monoids decidability min-automata max-automata Regular cost functions form a quantitative extension of regular languages that share the array of characterisations the latter possess. In this theory, functions are treated only up to preservation of boundedness on all subsets of the domain. In this work, we subject the well known distance automata (also called min-automata), and their dual max-automata to this framework, and obtain a number of effective characterisations in terms of logic, expressions and algebra. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Colcombet and Denis Kuperberg and Amaldev Manuel and Szymon Torunczyk 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.29 urn:nbn:de:0030-drops-57305 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.29 eng https://creativecommons.org/licenses/by/3.0/legalcode