Minimizing Deterministic Timed Finite State Machines. Issue 7 (2018)

• Record Type: Journal Article
• Authors: Bresolin, Davide; Tvardovskii, Aleksandr; Yevtushenko, Nina; Villa, Tiziano; Gromov, Maxim
• Is Part Of: IFAC-PapersOnLine. Volume 51:Issue 7(2018)
• Page Start: 486
• Page End: 492
• Publication Date: 2018
• Subjects: Timed Finite State Machines -- Minimization -- Real-time systems -- Automata theory -- Timed Automata; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2018.06.344
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: Timed automata and timed finite state machins (TFSMs) have been proposed to represent more accurately the behaviour of systems in continuous time. Recently, we introduced a model of TFSMs that extends the expressive power of FSMs by introducing a single clock, timed guards which restrict when the input/output transitions may happen, and timeouts on the transitions. We derived an abstraction procedure to convert a TFSM into an equivalent untimed FSM. Here, we extend the model with output timeouts and derive a minimal form for deterministic TFSMs that reduces the number of states, the number of transitions and the timeout values at each state.