?
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.
Saleh H., IEEE, 2023.
Estimating depth is necessary to understand and navigate the environment surrounding us. Over the years, many active sensors have been developed to measure depth, but they are expensive and require additional space for mounting. A cheaper alternative is estimating depth from a single RGB image taken by an ordinary monocular camera, which can be placed ...
Added: November 30, 2023
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
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, 2020Vol. 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
Switzerland: Springer International Publishing, 2021.
Added: September 28, 2021
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
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
Zelenov S. V., Zelenova S., , in: Lecture Notes in Computer ScienceVol. 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
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
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
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
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
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
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, ProceedingsVol. 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
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., , 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
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
Durandin O., Жильцова Л. П., В кн.: Дискретные модели в теории управляющих систем : IX Международная конференция, Москва и Подмосковье, 20-22 мая 2015 г.: Труды.: М.: МАКС Пресс, 2015. С. 74–75.
В работе исследуются переходные явления, возникающие в неразложимых стохастических КС-грамматиках. Переходные явления возникают в случае, когда перронов корень r матрицы первых моментов грамматики стремится слева к единице, т.е. происходит переход от докритического случая (r < 1) к критическому (r = 1) [1]. Для рассматриваемого случая получена асимптоти- ка условного математического ожидания M(t, τ ) числа ...
Added: January 18, 2017