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

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

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, Dries Van Dyck

Security, Guarding and Access Control

Research output › peer-review

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.

Original language	English
Pages (from-to)	891-911
Number of pages	21
Journal	Journal of Universal Computer Science
Volume	21
Issue number	7
DOIs	https://doi.org/10.3217/jucs-021-07-0891
State	Published - 1 Jul 2015

Access to Document

10.3217/jucs-021-07-0891License: Unspecified

http://www.jucs.org/jucs_21_7/naive_infinite_enumeration_ofLicense: Unspecified

Cite this

@article{37a96e68f1d54e3481dd799c6bd89a10,

title = "Naive infinite enumeration of context-free languages in incremental polynomial time",

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, Polynomial delay",

author = "{Costa Flor{\^e}ncio}, Christophe and Jonny Daenen and Jan Ramon and {Van Dyck}, Dries",

note = "Score=10",

year = "2015",

month = jul,

day = "1",

doi = "10.3217/jucs-021-07-0891",

language = "English",

volume = "21",

pages = "891--911",

journal = "Journal of Universal Computer Science",

issn = "0948-6968",

publisher = "Graz University of Technology, Institut f{\"u}r Informationssysteme und Computer Medien",

number = "7",

}

TY - JOUR

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

AU - Costa Florêncio , Christophe

AU - Daenen, Jonny

AU - Ramon, Jan

AU - Van Dyck, Dries

N1 - Score=10

PY - 2015/7/1

Y1 - 2015/7/1

N2 - 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.

AB - 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.

KW - Context-free grammar

KW - Systematic generation

KW - Incremental polynomial

KW - Polynomial delay

UR - http://ecm.sckcen.be/OTCS/llisapi.dll/open/31194237

U2 - 10.3217/jucs-021-07-0891

DO - 10.3217/jucs-021-07-0891

M3 - Article

SN - 0948-6968

VL - 21

SP - 891

EP - 911

JO - Journal of Universal Computer Science

JF - Journal of Universal Computer Science

IS - 7

ER -