ГлавнаяАрхивРЕШЕНИЕ ПАРАЛЛЕЛЬНЫХ УРАВНЕНИЙ ДЛЯ щ-ЯЗЫКОВ

РЕШЕНИЕ ПАРАЛЛЕЛЬНЫХ УРАВНЕНИЙ ДЛЯ щ-ЯЗЫКОВ | Прикладная дискретная математика. 2010. № 2(8).

Рассмотрена проблема решения параллельного уравнения для щ-языков. В частности, доказано, что, подобно уравнениям для регулярных языков, разрешимое уравнение всегда имеет наибольшее решение, формула которого имеет такой же вид, как и формула наибольшего решения для формальных языков. Показано также, что решение уравнения для щ-регулярных языков сводится к последовательности операций над полуавтоматами.
  • Title РЕШЕНИЕ ПАРАЛЛЕЛЬНЫХ УРАВНЕНИЙ ДЛЯ щ-ЯЗЫКОВ
  • Headline РЕШЕНИЕ ПАРАЛЛЕЛЬНЫХ УРАВНЕНИЙ ДЛЯ щ-ЯЗЫКОВ
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(8)
  • Date:
  • DOI
Ключевые слова
автоматные уравнения, параллельная композиция щ-языков, уравнения для щ-языков, условие Бюхи, automata equations, parallel composition of щ-languages, equations over щ-languages, Bьchi automata
Авторы
Ссылки
Yevtushenko N. V., Villa T., Brayton R. K., et al. Solution of Parallel Language Equations for Logic Synthesis // Proceedings of ICCAD 2001, San Jose. 2001. P. 103-110.
Wang G., Mishchenko A., Brayton R. K., et al. Sequential synthesis with co-Buchi specifications // ERL Technical Report, EECS Dept., UC Berkeley, April 2006. 6 p.
Thistle J. G., Wonham W. M. Supervision of infinte behavior of discrete-event systems // SIAM, Control and Optimization. 1994. V.32. No. 4. P. 1098-1113.
Buchi J. R. On a decision method in restricted second order arithmetic // Z. Math. Logik Grundlag. Math. 1960. P. 66-92.
Бушков В. Г., Евтушенко Н. В. Решение параллельных уравнений для щ-регулярных языков // Прикладная дискретная математика. Приложение. 2009. №1. С. 6-7.
Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (поведение и синтез). М.: Наука, 1970. 400 с.
Mukund M. Finite-state automata on infinite inputs // Tutorial talk, NSTCS 6, Banasthali, Rajasthan, India, August 1996. 32 p.
Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2008. 528 с.
РЕШЕНИЕ ПАРАЛЛЕЛЬНЫХ УРАВНЕНИЙ ДЛЯ щ-ЯЗЫКОВ | Прикладная дискретная математика. 2010. № 2(8).
РЕШЕНИЕ ПАРАЛЛЕЛЬНЫХ УРАВНЕНИЙ ДЛЯ щ-ЯЗЫКОВ | Прикладная дискретная математика. 2010. № 2(8).
Полнотекстовая версия