Studying homing and synchronizing sequences for Timed Finite State Machines with output delays
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918155343888384 |
|---|---|
| author | Vinarskii, Evgenii Ruszil, Jakub Roman, Adam Kushik, Natalia |
| author_facet | Vinarskii, Evgenii Ruszil, Jakub Roman, Adam Kushik, Natalia |
| contents | The paper introduces final state identification (synchronizing and homing) sequences for Timed Finite State Machines (TFSMs) with output delays and investigates their properties. We formally define the notions of homing sequences (HSs) and synchronizing sequences (SSs) for these TFSMs and demonstrate that several properties that hold for untimed machines do not necessarily apply to timed ones. Furthermore, we explore the applicability of various approaches for deriving SSs and HSs for Timed FSMs with output delays, such as truncated successor tree-based and FSM abstraction-based methods. Correspondingly, we identify the subclasses of TFSMs for which these approaches can be directly applied and those for which other methods are required. Additionally, we evaluate the complexity of existence check and derivation of (shortest) HSs / SSs for TFSMs with output delays. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_14526 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Studying homing and synchronizing sequences for Timed Finite State Machines with output delays Vinarskii, Evgenii Ruszil, Jakub Roman, Adam Kushik, Natalia Formal Languages and Automata Theory Computational Complexity The paper introduces final state identification (synchronizing and homing) sequences for Timed Finite State Machines (TFSMs) with output delays and investigates their properties. We formally define the notions of homing sequences (HSs) and synchronizing sequences (SSs) for these TFSMs and demonstrate that several properties that hold for untimed machines do not necessarily apply to timed ones. Furthermore, we explore the applicability of various approaches for deriving SSs and HSs for Timed FSMs with output delays, such as truncated successor tree-based and FSM abstraction-based methods. Correspondingly, we identify the subclasses of TFSMs for which these approaches can be directly applied and those for which other methods are required. Additionally, we evaluate the complexity of existence check and derivation of (shortest) HSs / SSs for TFSMs with output delays. |
| title | Studying homing and synchronizing sequences for Timed Finite State Machines with output delays |
| topic | Formal Languages and Automata Theory Computational Complexity |
| url | https://arxiv.org/abs/2507.14526 |