Two Size Measures for Timed Languages

Authors Eugene Asarin, Aldric Degorre



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2010.376.pdf
  • Filesize: 0.59 MB
  • 12 pages

Document Identifiers

Author Details

Eugene Asarin
Aldric Degorre

Cite AsGet BibTex

Eugene Asarin and Aldric Degorre. Two Size Measures for Timed Languages. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 376-387, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/LIPIcs.FSTTCS.2010.376

Abstract

Quantitative properties of timed regular languages, such as information content (growth rate, entropy) are explored. The approach suggested by the same authors is extended to languages of timed automata with punctual (equalities) and non-punctual (non-equalities) transition guards. Two size measures for such languages are identified: mean dimension and volumetric entropy. The former is the linear growth rate of the dimension of the language; it is characterized as the spectral radius of a max-plus matrix associated to the automaton. The latter is the exponential growth rate of the volume of the language; it is characterized as the logarithm of the spectral radius of a matrix integral operator on some Banach space associated to the automaton. Relation of the two size measures to classical information-theoretic concepts is explored.
Keywords
  • timed automata
  • entropy
  • mean dimension

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail