Минимизация автоматов с таймаутами и временными ограничениями

Конечные автоматы широко используются для анализа и синтеза управляющих систем. При описании систем, поведение которых зависит от времени, конечный автомат расширяется введением временных аспектов и вводится понятие временного автомата. В настоящей работе мы рассматриваем проблему минимизации автоматов с таймаутами и временными ограничениями, поскольку сложность многих задач в теории автоматов существенно зависит от размеров исследуемой системы. Поведение временного автомата может быть достаточно точно описано соответствующим конечным автоматом, и предлагаемый метод минимизации числа состояний системы основан на использовании такой конечно автоматной абстракции. Более того, далее мы минимизируем и временные аспекты автоматного описания, сокращая продолжительность таймаутов и число переходов с временными ограничениями. Мы также показываем, что для полностью определённого детерминированного временного автомата существует единственная минимальная (каноничная) форма, т. е. единственный приведённый по состояниям и временным аспектам автомат с таймаутами и временными ограничениями, поведение которого совпадает с исходным временным автоматом; например, такая минимальная форма может быть использована при построении проверяющих тестов для проверки функциональных и нефункциональных требований к тестируемой реализации. Предложенный метод к минимизации временных аспектов на основе конечно автоматной абстракции может быть применён и для частных случаев рассматриваемой модели, т. е. для минимизации детерминированных полностью определенных автоматов только с таймаутами или только с временными ограничениями.

временные автоматы, приведённая форма, минимальная форма

1. Gill A. Introduction to the Theory of Finite-State Machines. 1962, 207 p.

2. Lee, D., Yannakakis, M. (1996) Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE. 1996, 84(8), pp. 1090-1123.

3. Murphy T.E., Geng X.-J., Hammer J. On the control of asynchronous machines with races. IEEE Transactions on Automatic Control, 2003, 48(6), pp. 1073-1081.

4. Kumar R., Garg V.K. Modeling and control of logical discrete event systems. Kluwer Academic Publishers, 1995, 143 p.

5. Cassandras C. C., Lafortune S. Introduction to discrete event systems. Kluwer Academic Publishers, 1999, 822 p.

6. Dorofeeva R., El-Fakih K., Maag S., Cavalli A., Yevtushenko N. FSM-based conformance testing methods: A survey an-notated with experimental evaluation. Information and Software Technology, 2010, 52, pp. 1286-1297.

7. Zhigulin M., Yevtushenko N, Maag S., Cavalli A. FSM-Based Test Derivation Strategies for Systems with Time-Outs. Proc. of the 11th International Conference on Quality Software, QSIC 2011, IEEE, 2011. pp. 141-149.

8. El-Fakih K., Yevtushenko N., Fouchal H. Testing Timed Finite State Machines with Guaranteed Fault Coverage. TestCom/FATES, 2009, pp. 66-80.

9. Merayo M., Nunez M., Rodriguez I., Formal testing from timed finite state machines, Comput. Netw, 2008, 52 (2), 432-460.

10. Bresolin D., El-Fakih K., Villa T., Yevtushenko N. Deterministic Timed Finite State Machines: Equivalence Checking and Expressive Power. Intern Conf. GANDALF, 2014, pp. 203-216.

11. Твардовский А. С., Евтушенко Н. В. К минимизации автоматов с временными ограничениями. Вестник ТГУ. Управление, вычислительная техника и информатика, № 4 (29), 2014 г., стр. 77-83.

12. Твардовский А. С. К минимизации автоматов с таймаутами. Труды ИСП РАН, т. 26, вып. 6, 2014 г., стр. 77-84. DOI: 10.15514/ISPRAS-2014-26(6)-7