JUCS - Journal of Universal Computer Science 21(7): 891-911, doi: 10.3217/jucs-021-07-0891
Naive Infinite Enumeration of Context-free Languages in Incremental Polynomial Time
Christophe Costa Florêncio‡, Jonny Daenen§, Jan Ramon‡, Jan Van den Bussche§, Dries Van Dyck|‡ KU Leuven, Leuven, Belgium§ Hasselt University and Transnational University of Limburg, Limburg, Belgium| Belgian Nuclear Research Centre (SCK-CEN), Mol, Belgium
Corresponding author: Christophe Florêncio ( chris.costaflorencio@cs.kuleuven.be ) © Christophe Florêncio, Jonny Daenen, Jan Ramon, Jan Van den Bussche, Dries Dyck. This article is freely available under the J.UCS Open Content License. Citation:
Florêncio CC, Daenen J, Ramon J, Bussche JV, Dyck DV (2015) Naive Infinite Enumeration of Context-free Languages in Incremental Polynomial Time. JUCS - Journal of Universal Computer Science 21(7): 891-911. https://doi.org/10.3217/jucs-021-07-0891 |  |
Abstract
We consider the naive bottom-up concatenation scheme for a context-free language and show that this scheme has the incremental polynomial time property. This means that all members of the language can be enumerated without duplicates so that the time between two consecutive outputs is bounded by a polynomial in the number of strings already generated.
Keywords
context-free grammar, systematic generation, incremental polynomial time, polynomial delay