License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.33
URN: urn:nbn:de:0030-drops-48306
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4830/
Go to the corresponding LIPIcs Volume Portal

Kupferman, Orna ; Tamir, Tami

Properties and Utilization of Capacitated Automata (Invited Talk)

pdf-format:
5.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{kupferman_et_al:LIPIcs:2014:4830,
  author =	{Orna Kupferman and Tami Tamir},
  title =	{{Properties and Utilization of Capacitated Automata (Invited Talk)}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{33--44},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4830},
  URN =		{urn:nbn:de:0030-drops-48306},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.33},
  annote =	{Keywords: Automata, Capacitated transitions, Determinization, Maximum utilization}
}

Keywords: Automata, Capacitated transitions, Determinization, Maximum utilization
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI