Go home now Header Background Image
Search
Submission Procedure
share: |
 
Follow us
 
 
 
 
Volume 21 / Issue 7

available in:   PDF (169 kB) PS (367 kB)
 
get:  
Similar Docs BibTeX   Write a comment
  
get:  
Links into Future
 
DOI:   10.3217/jucs-021-07-0891

 

Naive Infinite Enumeration of Context-free Languages in Incremental Polynomial Time

Christophe Costa Florêncio (KU Leuven, Belgium)

Jonny Daenen (Hasselt University and Transnational University of Limburg, Belgium)

Jan Ramon (KU Leuven, Belgium)

Jan Van den Bussche (Hasselt University and Transnational University of Limburg, Belgium)

Dries Van Dyck (Belgian Nuclear Research Centre (SCK-CEN), Belgium)

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, incremental polynomial time, polynomial delay, systematic generation

Categories: F.2, F.4.2