www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/19674

Title: Naive Infinite Enumeration of Context-free Languages in Incremental Polynomial Time
Authors: Florencio, Christophe Costa
Daenen, Jonny
Ramon, Jan
Van den Bussche, Jan
Van Dyck, Dries
Issue Date: 2015
Publisher: GRAZ UNIV TECHNOLGOY, INST INFORMATION SYSTEMS COMPUTER MEDIA-IICM
Citation: JOURNAL OF UNIVERSAL COMPUTER SCIENCE, 21 (7), p. 891-911
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.
Notes: [Florencio, Christophe Costa; Ramon, Jan] Katholieke Univ Leuven, Leuven, Belgium. [Daenen, Jonny; Van den Bussche, Jan] Hasselt Univ, Hasselt, Belgium. [Daenen, Jonny; Van den Bussche, Jan] Transnat Univ Limburg, Limburg, Belgium. [Van Dyck, Dries] Belgian Nucl Res Ctr SCK CEN, BE-2400 Mol, Belgium.
URI: http://hdl.handle.net/1942/19674
ISI #: 000358989800002
ISSN: 0948-695X
Category: A1
Type: Journal Contribution
Validation: ecoom, 2016
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A385.88 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.