On the regularity of languages generated by context-free evolutionary grammars

Authors
Dassow, J Paun, G
Citation
J. Dassow et G. Paun, On the regularity of languages generated by context-free evolutionary grammars, DISCR APP M, 92(2-3), 1999, pp. 205-209
Citations number
6
Categorie Soggetti
Engineering Mathematics
Journal title
DISCRETE APPLIED MATHEMATICS → ACNP
Volume
92
Issue
2-3
Year of publication
1999
Pages
205 - 209
Database
ISI
SICI code
Abstract
We show that there is a regular language which cannot be generated by conte xt-free evolutionary grammars, thus disproving a conjecture from Dassow et al. (BioSystems 43 (1997) 169-177). However, all regular languages which ar e strictly bounded can be generated by context-free evolutionary grammars. (C) 1999 Elsevier Science B.V. All rights reserved.