Send us a comment.
For technical introductions to FSTNs and discussion of some of their formal properties, see Aho and Ullman (1972, Sections 2.2 and 2.3), [*] Aho and Ullman (1977, Chapter 3), [*] Hopcroft and Ullman (1979, Chapter 2), or [*] Gersting (1982, Chapters 7 and 8). [*] Relevant accounts of directed graphs and graph traversal algorithms are to be found in Aho et al.(1982, Chapter 6) and [*] Sedgwick (1983, Chapters 29-30). [*] Technical presentations of FSTs are available in Lynch and Pierson (1968) [*] Lewis and Stearns (1968), [*] and Aho and Ullman (1972, Sections 3.1 and 3.3). [*] Useful background reading on NLP uses of transition networks and pattern matching is provided by Winograd (1983, Chapter 2). [*] Some researchers have continued to take an interest in finite-state devices for syntactic parsing: Blank (1985), Brodda (1986), [*] [*] Ejerhed (1982), Ejerhed and Church (1983), Langendoen and Langsam (1984), and Pulman (1986), for example. [*] [*] [*] [*]
The formal properties of the morphology of Bambara, mentioned above, are the subject of Culy (1985). [*] Other work relevant to the question of the adequacy of finite-state machinery for phonological and morphological processing purposes includes Langendoen (1981), Carden (1983), Church (1983b, pp.116-17), [*] [*] [*] and Gazdar and Pullum (1985). [*] Further details of the morphology of Swahili are to be found in Perrott (1951). [*] ENG-MONOSYL is loosely based on the English phonotactics to be found in Whorf (1940). [*]
The applicability of FSTs in phonology was noticed almost immediately. Johnson (1970/72) proved that a phonology that permitted only simultaneous [*] rule application, as opposed to iterative derivational application, was equivalent to an FST. A decade later, Kaplan and Kay presented a paper in which they showed how the iteratively applied rules of standard generative phonology could, individually, be algorithmically compiled into FSTs. The closest thing to a published account of this work can be found in Kay (1983, pp.100-4). [*] Kaplan and Kay's work directly influenced that of Koskenniemi (1983a, 1983b, 1984) which, in turn, led to [*] [*] [*] that of Karttunen and his students on the KIMMO system (Gajek et al. 1983, Khan et al. 1983, and Karttunen 1983). [*] [*] [*] The Koskenniemi-style approach is described and evaluated in Gazdar (1985). [*] Finite-state phonology or morphology fragments exist for Arabic (Kay 1987), [*] Japanese (Alam 1983), Rumanian (Khan 1983), French (Lun 1983), German (Görz and Paulus 1988), [*] [*] [*] [*] Semitic (Kataja and Koskenniemi 1988), [*] Spanish (Meya 1987), Old Church Slavonic (Lindstedt 1984), Swedish (Bl~Aberg 1984), [*] [*] [*] Turkish (Hankamer 1986) [*] and English (Karttunen and Wittenberg 1983, Russell et al. 1986, Black et al. 1987). [*] [*] [*] Some interesting complexity results relevant to this approach are presented in Barton et al.(1987, Chapters 5 and 6), [*] to which Koskenniemi and Church (1988) replies. [*] Further theoretical developments are reported in Bear (1988), [*] Carson (1988), [*] and Reape and Thompson (1988). [*] The potential role of finite-state parsing in speech recognition is the subject of Church (1983a), [*] while Gibbon (1987) proposes [*] its use for the processing of tone systems.
Good introductions to the notion of search spaces and search techniques are given by Raphael (1976), [*] Nilsson (1980, Chapter 1), [*] Barr and Feigenbaum (1981, Chapter II), [*] Rich (1983, Chapters 2-4), [*] Charniak and McDermott (1985, Chapter 5), [*]
and Winston (1984, Chapter 4). [*] Pearl (1984) provides a definitive reference on the topic. [*]
Code:library.pl
Send us a comment.