Computing the Bandwidth of Meager Timed Automata
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917700104617984 |
|---|---|
| author | Asarin, Eugene Degorre, Aldric Dima, Catalin Inclán, Bernardo Jacobo |
| author_facet | Asarin, Eugene Degorre, Aldric Dima, Catalin Inclán, Bernardo Jacobo |
| contents | The bandwidth of timed automata characterizes the quantity of information produced/transmitted per time unit. We previously delimited 3 classes of TA according to the nature of their asymptotic bandwidth: meager, normal, and obese. In this paper, we propose a method, based on a finite-state simply-timed abstraction, to compute the actual value of the bandwidth of meager automata. The states of this abstraction correspond to barycenters of the faces of the simplices in the region automaton. Then the bandwidth is $\log 1/|z_0|$ where $z_0$ is the smallest root (in modulus) of the characteristic polynomial of this finite-state abstraction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_12694 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing the Bandwidth of Meager Timed Automata Asarin, Eugene Degorre, Aldric Dima, Catalin Inclán, Bernardo Jacobo Formal Languages and Automata Theory 68Q70, 68Q45, 68P30 F.4.3; E.4; F.1.1 The bandwidth of timed automata characterizes the quantity of information produced/transmitted per time unit. We previously delimited 3 classes of TA according to the nature of their asymptotic bandwidth: meager, normal, and obese. In this paper, we propose a method, based on a finite-state simply-timed abstraction, to compute the actual value of the bandwidth of meager automata. The states of this abstraction correspond to barycenters of the faces of the simplices in the region automaton. Then the bandwidth is $\log 1/|z_0|$ where $z_0$ is the smallest root (in modulus) of the characteristic polynomial of this finite-state abstraction. |
| title | Computing the Bandwidth of Meager Timed Automata |
| topic | Formal Languages and Automata Theory 68Q70, 68Q45, 68P30 F.4.3; E.4; F.1.1 |
| url | https://arxiv.org/abs/2406.12694 |