Search
 
loader loading subjects...
cover
On the Lower Bounds for Asymmetrical Insertion-deletion Languages
Gemma Bel-Enguix, Alexander Krassovitskiy, Yurii Rogozhin, Sergey Verlan
145 - 154
10.3233/978-1-60750-762-8-145
Frontiers in Artificial Intelligence and Applications
Volume 228: Biology, Computation and Linguistics
Abstract

This article investigates languages generated by insertion-deletion systems of small size. Four classes of asymmetrical insertion-deletion systems are considered; two of them are known to be computationally uncomplete. We show a series of proper inclusions that permit to determine some non-trivial lower bounds for the corresponding languages.

$35.00 / €27.50 / £22.00
Add PDF to cart