### ?

## Minimizing Deterministic Timed Finite State Machines

P. 486-492.

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.

Switzerland : Springer, 2016

Control and analysis of the timing of computations are crucial to many domains of system engineering, be it, e.g., for ensuring a timely response to stimuli originating in an uncooperative environment or for synchronizing components in VLSI. Reflecting this broad scope, timing aspects of systems from a variety of domains have been treated independently by ...

Added: September 13, 2016

Vladimir A. Bashkin, Lomazova I. A., Novikova Y., , in : Parallel Computing Technologies. 12th International Conference, PaCT 2013, St. Petersburg, Russia, September 30-October 4, 2013, Proceedings. Vol. 7979: Lecture Notes in Computer Science.: Berlin, Heidelberg : Springer, 2013. P. 13-25.

The paper presents a formalism and a tool for modelling and analysis of distributed real-time systems of mobile agents. For that we use a time extension of our Resource Driven Automata Nets (TRDA-nets) formalism. A TRDA-net is a two-level system. The upper level represents distributed environment locations with a net of active resources. On the ...

Added: October 1, 2013

Tvardovskii A. S., N. V. Yevtushenko, Proceedings of the Institute for System Programming of the RAS 2020 Vol. 32 No. 2 P. 125-134

Trace models such as Finite State Machines (FSMs) are widely used in the area of analysis and synthesis of discrete event systems. FSM minimization is a well-known optimization problem which allows to reduce the number of FSM states by deriving the canonical form that is unique up to isomorphism. In particular, the latter is a ...

Added: October 30, 2020

Springer, 2020

Added: October 22, 2018

Zelenova S. A., Zelenov S. V., Proceedings of the Institute for System Programming of the RAS 2017 Vol. 29 No. 6 P. 183-202

In the paper, we address mission critical systems, such as automobile, avionic, mobile robotic, telecommunication, etc. Such systems must meet hard real-time constraints in order to avoid catastrophic consequences. To meet the real-time constraints, strict periodicity is used (i.e. for any periodic task, time between release points is constant). Sensors, actuators and feedback control functions ...

Added: August 11, 2018

Tvardovskii A., El-Fakih K., Nina Yevtushenko, , in : Lecture Notes in Computer Science (Volume 11146, ICTSS2018). : Springer, 2018. P. 149-154.

In contrast to untimed FSMs, two minimal initialized FSMs with timeouts can be equivalent but not isomorphic. Accordingly, we propose an appropriate fault model and a method for complete test derivation for initialized deterministic FSMs with timeouts based on an appropriate FSM abstraction of the timed FSM specification. We also show how the same approach ...

Added: November 1, 2018

Vyalyi M., Rubtsov A. A., Проблемы передачи информации 2015 Т. 51 № 4 С. 47-59

We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance ...

Added: February 14, 2016

Babash A. V., , in : Proceedings of the 10th International Scientific and Practical Conference named after A. I. Kitov "Information Technologies and Mathematical Methods in Economics and Management (IT&MM-2020)"/, Moscow, Russia, October 15-16, 2020. Vol. 2830.: CEUR Workshop Proceedings, 2021. P. 337-359.

A trapdoor cipher is a cipher whose algorithm contains some hidden structure (a trapdoor) providing the existence of a subliminal information channel. In cryptographic practice, there could be situations when a constructed cipher may contain some critical defect (a trapdoor) whose identification can significantly weaken the cryptographic strength of this cipher. In this paper, we ...

Added: November 2, 2021

Elsevier, 2018

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 ...

Added: November 1, 2018

Zelenov S. V., Зеленова С. А., Программирование 2018 Т. 44 № 3 С. 3-16

A new look at the problem of constructing a scheduler in the case of a group of strictly periodic tasks is proposed. The structure of the system of periods is represented in terms of graph theory. A criterion for the existence of a conflict-free schedule based on this representation is obtained, and generic schemes of ...

Added: March 15, 2018

Rubtsov A. A., Vyalyi M., Information and Computation 2019

We consider a computational model which is known as set automata. The set automata are one-way finite automata with an additional storage— the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by M. Kutrib, A. Malcher, M. Wendlandt ...

Added: October 22, 2018

Rubtsov A. A., Vyalyi M., , in : Descriptional Complexity of Formal Systems. Vol. 9118.: Switzerland : Springer, 2015. P. 256-267.

We investigate regular realizability (RR) problems, which are the prob- lems of verifying whether intersection of a regular language – the input of the problem – and fixed language called filter is non-empty. In this pa- per we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse ...

Added: August 25, 2015

Zelenov S. V., Zelenova S., , in : Lecture Notes in Computer Science. Vol. 11964: Perspectives of System Informatics.: Springer, 2019. P. 214-222.

In the paper, we suggest new approach to schedulability problem for strict periodic tasks (a periodic task is strict if it must be started in equal intervals of time – task’s period). Given permissible tasks’ periods, our approach allows to obtain quickly all schedulable sets of tasks with such periods and to build immediately a ...

Added: February 19, 2020

Ekaterinburg : Ural Fedearal University, 2014

Added: October 17, 2014

Rubtsov A. A., , in : Proceedings of Language and Automata Theory and Applications 2020. : Springer, 2020.

Formal grammars provide the way of formal language's description. The other way is describing a language by automata model. But not all classes of formal languages fit in the both ways of description. We provide a new way of formal language's description which is universal and combine the advantages of the both mentioned methods — a ...

Added: October 19, 2017

Suleykin A., Peter B. Panfilov, , in : 2022 8th International Conference on Control, Decision and Information Technologies (CoDIT). : IEEE, 2022. P. 1495-1500.

In this work, benchmarking of production plan processing applications based on data storage and analytics solutions using open source technologies was performed. The functional and component architecture of a digital framework for processing production plan files is presented, with special attention to the performance analysis of data processing based on the measurement of processing time ...

Added: September 23, 2022

Cham : Springer, 2017

The 21st International Conference on Developments in Language Theory (DLT 2017) was organized by the Department of Mathematics of the University of Liège, Belgium, during August 7–11, 2017.
The DLT conference series is one of the major international conference series in language theory and related areas. The DLT conference was established by G. Rozenberg and A. ...

Added: September 5, 2017

Rubtsov A. A., Vyalyi M., , in : Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Vol. 10846.: Springer, 2018. P. 295-307.

We consider a computational model which is known as set automata.
The set automata are one-way finite automata with an additional storage—the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by Kutrib et al. in 2014 in [2, 3].
In this ...

Added: June 21, 2018

Chistikov D., Mikhail Vyalyi, , in : LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science. Saarbrücken, Germany. July, 2020. : Association for Computing Machinery (ACM), 2020. P. 312-326.

Added: September 4, 2020

Rubtsov A. A., , in : Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. : Cham : Springer, 2018. P. 553-565.

We present a new structural lemma for deterministic con- text free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions that makes it much easier to apply. The structural lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), ...

Added: September 12, 2018

Switzerland : Springer International Publishing, 2021

Added: September 28, 2021

Cham : Springer, 2018

This volume of Lecture Notes in Computer Science contains the papers presented at the 22nd International Conference on Developments in Language Theory (DLT 2018) organized by the Algorithmic “Oritatami” Self-Assembly Laboratory as part of the 100th Anniversary Commemorative Events of University of Electro-Communications (UEC) in Fuchu, Tokyo, Japan, during September 10–14, 2018.
The DLT conference series is one ...

Added: September 12, 2018

Rubtsov Alexander, , in : Abstracts of Reports and other materials of the 7th School "Computer Science Days in Ekaterinburg". : Ekaterinburg : Ural Fedearal University, 2014. P. 25-27.

Added: October 17, 2014

Rubtsov A. A., Vyalyi M., , in : Developments in Language Theory 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings. : Cham : Springer, 2017. P. 332-344.

We consider a computational model which is known as set automata. The set automata are one-way finite automata with an additional storage---the set. There are two kinds of set automata---the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by M. Kutrib, A. Malcher, M. Wendlandt in ...

Added: September 5, 2017