Searching for grammaticality

Propagating dependencies in the Viterbi algorithm

Stephen Wan*, Robert Dale, Mark Dras, Cécile Paris

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

9 Citations (Scopus)


In many text-to-text generation scenarios (for instance, summarisation), we encounter human-authored sentences that could be composed by recycling portions of related sentences to form new sentences. In this paper, we couch the generation of such sentences as a search problem. We investigate a statistical sentence generation method which recombines words to form new sentences. We propose an extension to the Viterbi algorithm designed to improve the grammaticality of generated sentences. Within a statistical framework, the extension favours those partially generated strings with a probable dependency tree structure. Our preliminary evaluations show that our approach generates less fragmented text than a bigram baseline.

Original languageEnglish
Title of host publicationProceedings of the 10th European Workshop on Natural Language Generation, ENLG-05
EditorsGraham Wilcock, Kristiina Jokinen, Chris Mellish, Ehud Reiter
Place of PublicationAberdeen, UK
Number of pages6
Publication statusPublished - 2005
Event10th European Workshop on Natural Language Generation, ENLG-05 - Aberdeen, United Kingdom
Duration: 8 Aug 200510 Aug 2005


Other10th European Workshop on Natural Language Generation, ENLG-05
CountryUnited Kingdom

Fingerprint Dive into the research topics of 'Searching for grammaticality: Propagating dependencies in the Viterbi algorithm'. Together they form a unique fingerprint.

Cite this