|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Minimal Union-Free Decompositions of Regular Languagesстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Дата последнего поиска статьи во внешних источниках: 19 июля 2013 г.
- Авторы: Afonin S., Golomazov D.
- Сборник: Proceedings of the 3rd International Conference on Language and Automata Theory and Applications
- Серия: Lecture Notes in Computer Science
- Том: 5457
- Год издания: 2009
- Первая страница: 83
- Последняя страница: 92
- DOI: 10.1007/978-3-642-00982-2_7
- Аннотация: A regular language is called union-free if it can be represented by a regular expression that does not contain the union operation. Every regular language can be represented as a finite union of union-free languages (the so-called union-free decomposition), but such decomposition is not necessarily unique. We call the number of components in the minimal union-free decomposition of a regular language the union width of the regular language. In this paper we prove that the union width of any regular language can be effectively computed and we present an algorithm for constructing a corresponding decomposition. We also study some properties of union-free languages and introduce a new algorithm for checking whether a regular language is union-free.
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | union-free-decomposition.pdf | 133,5 КБ | 19 декабря 2011 [safonin] |