# Generating All Circular Shifts by Context-Free Grammars in Chomsky Normal Form

Asveld, P.R.J.
(2006)
*Generating All Circular Shifts by Context-Free Grammars in Chomsky Normal Form.*
Journal of Automata, Languages and Combinatorics, 11
(2).
pp. 147-159.
ISSN 1430-189X

PDF
Restricted to UT campus only : Request a copy 171kB |

Abstract: | Let be an alphabet of symbols and let be the language of circular shifts of the word ; so . We discuss a few families of context-free grammars () in Chomsky normal form such that generates . The grammars in these families are inverstigated with respect to their descriptional complexity, i.e., we determine the number of nonterminal symbols and the number of rules of as functions of . These and happen to be functions bounded by low-degree polynomials, particularly when we focus our attention to unambiguous grammars. Finally, we introduce a family of minimal unambiguous grammars for which and are linear. |

Item Type: | Article |

Additional information: | The paper is in the 2006-volume of Journal of Automata, Languages and Combinatorics; however, this volume appeared in 2008. This journal has no PDF-repository and no DOI's. |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Link to this item: | http://purl.utwente.nl/publications/62108 |

Official URL: | http://jalc.de/ |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 248491