The Library
The information rate and other parameters of probabilistic context free grammars and their parsers
Tools
Tools
Tools
Kestner, Simon (1974) The information rate and other parameters of probabilistic context free grammars and their parsers. PhD thesis, University of Warwick.
|
PDF
WRAP_Thesis_Kestner_1974.pdf - Requires a PDF viewer. Download (6Mb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b1746800~S1
Abstract
Probabilistic context-free languages are defined by giving predetermined probabilities (preprobabilities) for the choices that their grammars make when generating.
Chapter 1 shows how to carry out the above definition, and how to calculate some parameters or the language; for instance: average length or work, mean square length, digraph probabilities, entropy.
Chapter 2 introduces generating ffunctions related to grammars. It uses them to derive a condition for which preprobabilities give rise to well-fformed probability spaces. Two ffunctions, the length and entropy generating ffunctions are studied in detail. They are algebraic ffunctions, can in general only be defined implicitly, but can be used to give unified explicit methods or calculating all the parameters or chapter I (and more).
Chapter 3 defines and shows how to calculate the information rate or a language. As a by-blow, Macmillan's theorem is extended (for a small class or processes) to an analogue or the Central Limit Theorem.
Chapter 4 tries to compare the efficiencies or different parsing algorithms. In a reasonable sense, all deterministic parsers take equal average time to parse, any backtracking parser is slower, but there is no general algorithm for calculating the speed or a backtracking parser.
| Item Type: | Thesis (PhD) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science) | ||||
| Library of Congress Subject Headings (LCSH): | Natural language processing (Computer science), Probabilities, Parsing (Computer programs), Computational linguistics | ||||
| Official Date: | September 1974 | ||||
| Dates: |
|
||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Thesis Type: | PhD | ||||
| Publication Status: | Unpublished | ||||
| Supervisor(s)/Advisor: | Park, David | ||||
| Extent: | 176 leaves | ||||
| Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
