Naive infinite enumeration of context-free languages in incremental polynomial time

Christophe Costa Florêncio , Jonny Daenen, Jan Ramon, Dries Van Dyck

Research outputpeer-review


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.
Original languageEnglish
Pages (from-to)891-911
Number of pages21
JournalJournal of Universal Computer Science
Issue number7
StatePublished - 1 Jul 2015

Cite this