|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
The concurrency complexity for the Horn fragment of linear logicстатья
- Автор: Dudakov Sergey M.
- Сборник: Logical Foundations of Computer Science, 4th International Symposium, LFCS'97, Yaroslavl, Russia, July 6-12, 1997, Proceedings
- Редактор: Адян Сергей Иванович
- Серия: Lecture Notes in Computer Science
- Том: 1234
- Год издания: 1997
- Место издания: Springer-Verlag Berlin
- Первая страница: 78
- Последняя страница: 87
- DOI: 10.1007/3-540-63045-7_9
- Аннотация: The provability problem for the Horn fragment of linear logic is NP-complete. In this work we investigate various definitions of concurrency proposed in and establish the complexity of the provability problem and the problem of concurrency recognition. The notion of k-maximal concurrency is introduced which guarantees polynomial time provability. Theorems on hierarchy and on complexity of recognition of the property are proved.
- Добавил в систему: Золин Евгений Евгеньевич