Cut point languages of markov DTOL systems |
| |
| Authors: | H. Jürgensen D. E. Matthews D. Wood |
| |
| Affiliation: | (1) Institut für theoretische Informatik, Technische Hochschule Darmstadt, Magdalenestr. 11, D-6100 Darmstadt, Germany;(2) Department of Statistics, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada;(3) Unit for Computer Science, McMaster University, L8S 4K1 Hamilton, Ontario, Canada |
| |
| Abstract: | Letp satisfy 0  p < 1, then by  (p) we denote the family of Markov DTOL languages with cut pointp. In this paper we present a complete classification of the collection of such families (p), 0 p < 1, showing that forms an infinite nondense hierarchy with (0) being its only accumulation point from below. Furthermore it is proved that each language in (p) can be expressed as a finite union of DDTOL languages.Work supported partially by the Natural Sciences and Engineering Research Council of Canada grants Nos. A-3590 and A-7700, and partially by Deutsche Forschungsgemeinschaft. |
| |
| Keywords: | Markov DTOL systems cut-point stochastic grammars probabilistic grammars language family collection of language families dense hierarchy accumulation point |
| 本文献已被 SpringerLink 等数据库收录！ |
|
