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 | Source: | 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. | Keywords: | context-free grammar; systematic generation; polynomial time;context-free grammar; systematic generation; incremental polynomial time; polynomial delay | Document URI: | http://hdl.handle.net/1942/19674 | ISSN: | 0948-695X | e-ISSN: | 0948-6968 | ISI #: | 000358989800002 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2016 |
| Appears in Collections: | Research publications |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| authorversion.pdf | 385.88 kB | Adobe PDF | View/Open |
WEB OF SCIENCETM
Citations
5
checked on Apr 24, 2024
Page view(s)
50
checked on Apr 17, 2023
Download(s)
8
checked on Apr 17, 2023
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.