2026-07-22T12:53:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4830 2024-03-06T10:35:23Z ddc:004 open_access

Properties and Utilization of Capacitated Automata (Invited Talk) Kupferman, Orna Tamir, Tami Automata Capacitated transitions Determinization Maximum utilization We study capacitated automata(CAs), where transitions correspond to resources and may have bounded capacities. Each transition in a CA is associated with a (possibly infinite) bound on the number of times it may be traversed. We study CAs from two points of view. The first is that of traditional automata theory, where we view CAs as recognizers of formal languages and examine their expressive power, succinctness, and determinization. The second is that of resource-allocation theory, where we view CAs as a rich description of a flow network and study their utilization. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Orna Kupferman and Tami Tamir 2014 Is Part Of LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2014.33 urn:nbn:de:0030-drops-48306 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.33 eng https://creativecommons.org/licenses/by/3.0/legalcode