Studying homing and synchronizing sequences for Timed Finite State Machines with output delays Journal: Journal of Computational and Applied Mathematics
Evgenii Vinarskii, Jakub Ruszil, Adam Roman, Natalia Kushik · 2025
Read Studying homing and synchronizing sequences for Timed Finite State Machines with output delays Journal: Journal of Computational and Applied Mathematics by Evgenii Vinarskii, Jakub Ruszil, Adam Roman, Natalia Kushik (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-14526.txt.
Introduction
Evgenii Vinarskii and co-authors study test sequences for timed machines whose outputs arrive late, in this 2025 paper. A homing sequence lets a tester pin down a machine's final state from its replies; a synchronizing sequence forces the machine into one known state. Both are staples of testing ordinary state machines.
Timing breaks some of the old rules, the authors show, so tricks that work for untimed machines can fail here. They sort out which machine subclasses still allow tree-based or abstraction-based derivations, and weigh how hard it is even to tell whether such sequences exist or to find the shortest ones.
Catalog record
| CREATOR | Evgenii Vinarskii, Jakub Ruszil, Adam Roman, Natalia Kushik |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-14526
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Studying homing and synchronizing sequences for Timed Finite State Machines with output delays Journal: Journal of Computational and Applied Mathematics Evgenii Vinarskii, Jakub Ruszil, Adam Roman, Natalia Kushik Abstract 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 (original) methods are required. Additionally, we evaluate the complexity of existence check and derivation of (shortest) HSs / SSs for TFSMs with output delays. 1 Introduction Timed FSMs and Timed Automata (TAs) are widely used in model-based testing and verification of real-time reactive systems [ 10 ] . Quite often, the current state of the system under analysis is unknown, and in this case, it is necessary to first bring the system to a known, stable state to further continue its analysis (e.g., apply the test cases, verify certain properties, etc.). Being fundamental in the theory of FAs and FSMs, synchronizing and homing sequences [ 15 ] allow the system to be set to a known state. This paper studies the properties of SSs and HSs for TFSMs with output delays; such sequences serve as a base for ‘gedanken’ [ 7 ] synchronizing and homing experiments, designed to identify a machine’s final state, i.e., the state after the sequence has been applied. In the context of FAs and FSMs, a synchronizing experiment involves applying an SS to bring the machine to a known state, regardless of its initial state. A homing experiment, on the contrary, involves not only applying the sequence but also observing the corresponding output response on it, to determine the final state. For real-time systems, modeled with Timed FSMs [ 22 ] , the concept of the ‘gedanken’ experiments should be extended to consider the timed aspects for both inputs and outputs. These steps have already been taken in the literature; for example, in [ 8 ] and [ 19 ] , the authors extend the classical experiment by associating inputs (or events) with timestamps. In this paper, we add an additional observation point at the output channel, capturing both inputs and outputs with precise timestamps. In this setting, inputs are applied and outputs are produced with these timestamps, and that sometimes increases the complexity of the final state identification problem. Key research challenges in the domain include the decidability and computational complexity of the existence check of SSs and HSs, as well as deriving, whenever possible, shortest sequences of this kind. The derivation of SSs and HSs for classical FAs and FSMs has been extensively studied and summarized by S. Sandberg [ 15 ] , along with algorithms for deriving these sequences. These algorithms can be grouped by: (i) iterative approaches which construct SS (or HS) for the entire machine by combining those derived for every pair of states [ 6 ] , [ 14 ] , [ 15 ] [ 21 ] , (ii) successor tree-based approaches [ 11 ] , which operate on the sets of states by iteratively splitting or merging them at each step, and (iii) solver-based approaches ( [ 17 ] and [ 18 ] ) that formulate the conditions for a machine to be synchronized (homed) using a satisfiable formula. For complete deterministic FSMs, checking the existence of HSs (SSs) is relatively straightforward and can be performed in polynomial time, while the problem of the derivation of a shortest HS and SS is NP-hard [ 15 ] . For non-deterministic but observable FSMs and non-deterministic and partial FAs the problem becomes PSPACE-hard [ 4 ] , [ 9 ] , [ 17 ] . This paper explores various strategies for deriving SSs and HSs for the TFSM with output delays considered in [ 22 ] and [ 23 ] . In the TFSM with output delays, each input/output transition is associated with a timed guard (interval) and an output delay. A transition is executed only when the timed input satisfies the guard. The output delay represents the time required to produce the output after the input is applied. Note that the TFSM can accept an input while the output of the previous one has not yet been produced. This implies that the TFSM supports the concurrent execution of procedures (for handling inputs and generating outputs), as detailed in Section 2 . Therefore, the TFSM of interest has the following features: (i) it operates as a timed input/output automaton, allowing inputs to be accepted without waiting for their corresponding outputs, and (ii) it preserves the FSM property that the length of the input sequence is the same as the length of the corresponding output response. This affects the properties of SSs and HSs for the TFSM of interest. For example, we show that for these TFSMs, not every prolongation of a homing sequence is a homing sequence. The latter does not allow to “directly” adapt the iterative approaches for deriving an HS for the TFSM with output delays. Despite this, we demonstrate that so-called non-integer timed input sequences exist, for which the prolongation on both sides preserves the homing property. Thus, we adapt the truncated successor tree approach [ 12 ] to derive a shortest HS (SS) for the TFSM of interest. Another approach for deriving SSs and HSs for a timed machine is to reduce the problem to the derivation of SSs and HSs for an untimed abstraction of the timed machine. This reduction is typically achieved through the construction of region automaton / FSM (see for example [ 1 ] , [ 2 ] , [ 19 ] , [ 20 ] , [ 5 ] ). The authors in [ 19 ] and [ 20 ] have proven that this reduction can be effectively applied to Timed FSMs with timed guards [ 19 ] and Timed FSMs with timeouts [ 20 ] . However, the same reduction cannot be directly adapted for the Timed FSMs with output delays considered in this paper. To address this, we propose modifying the FSM abstraction introduced in [ 20 ] to facilitate the derivation of SSs and HSs. The latter motivates us to study the properties of the correspondence between SSs and HSs for the TFSMs with output delays and their untimed abstractions. It also involves comparing the complexity of the existence check of HSs (SSs) and the derivation of a shortest HS (SS) for both, timed and untimed machines. The main contributions of this paper are the following: (i) the introduction and definition of homing and synchronizing sequences for TFSMs with output delays, (ii) HS and SS existence check and derivation strategies for TFSMs, together with the relevant complexity analysis, and (iii) a study of various TFSM classes for which successor-tree based approaches and/or FSM abstractions are applicable