From Double Pushout Grammars to Hypergraph Lambek Grammars With and Without Exponential Modality

Автор: Pshenitsyn Tikhon
Сборник: Proceedings Twelfth International Workshop on Computing with Terms and Graphs (TERMGRAPH 2022)
Серия: Electronic Proceedings in Theoretical Computer Science
Том: 377
Год издания: 2023
Место издания: Open Publishing Association
Первая страница: 9
Последняя страница: 26
DOI: 10.4204/eptcs.377.1
Аннотация: We study how to relate well-known hypergraph grammars based on the double pushout (DPO) approach and grammars over the hypergraph Lambek calculus HL (called HL-grammars). It turns out that DPO rules can be naturally encoded by types of HL using methods similar to those used by Kanazawa for multiplicative-exponential linear logic. In order to generalize his reasonings we extend the hypergraph Lambek calculus by adding the exponential modality, which results in a new calculus HMEL0; then we prove that any DPO grammar can be converted into an equivalent HMEL0-grammar. We also define the conjunctive Kleene star, which behaves similarly to this exponential modality, and establish a similar result. If we add neither the exponential modality nor the conjunctive Kleene star to HL, then we can still use the same encoding and show that any DPO grammar with a linear restriction on the length of derivations can be converted into an equivalent HL-grammar.
Добавил в систему: Пшеницын Тихон Григорьевич

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ИНХС РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА