109 urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891 JUCS - Journal of Universal Computer Science jucs 0948-695X 0948-6968 Journal of Universal Computer Science 10.3217/jucs-021-07-0891 23337 Research Article F.2 - ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY F.4.2 - Grammars and Other Rewriting Systems Naive Infinite Enumeration of Context-free Languages in Incremental Polynomial Time Florêncio Christophe Costa chris.costaflorencio@cs.kuleuven.be 1 Daenen Jonny 2 Ramon Jan 1 Bussche Jan Van den 2 Dyck Dries Van 3 KU Leuven, Leuven, Belgium KU Leuven Leuven Belgium Hasselt University and Transnational University of Limburg, Limburg, Belgium Hasselt University and Transnational University of Limburg Limburg Belgium Belgian Nuclear Research Centre (SCK-CEN), Mol, Belgium Belgian Nuclear Research Centre (SCK-CEN) Mol Belgium

Corresponding author: Christophe Costa Florêncio (chris.costaflorencio@cs.kuleuven.be).

Academic editor:

2015 01 07 2015 21 7 891 911 B5824AE5-3C76-5588-AC13-23A59361B39A 5505323 14 02 2014 19 05 2015 Christophe Costa Florêncio, Jonny Daenen, Jan Ramon, Jan Van den Bussche, Dries Van Dyck This article is freely available under the J.UCS Open Content License.

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.