Realization of natural language interfaces using lazy functional programming

ABSTRACT

The construction of natural language interfaces to computers continues to be a major challenge. The need for such interfaces is growing now that speech recognition technology is becoming more readily available, and people cannot speak those computer-oriented formal languages that are frequently used to interact with computer applications. Much of the research related to the design and implementation of natural language interfaces has involved the use of high-level declarative programming languages. This is to be expected as the task is extremely difficult, involving syntactic and semantic analysis of potentially ambiguous input. The use of LISP and Prolog in this area is well documented. However, research involving the relatively new lazy functional programming paradigm is less well known. This paper provides a comprehensive survey of that research.

REFERENCES

• 1: Abdullah, N. 2003. Two set-theoretic approaches to the semantics of adjective-noun combinations. M.S. thesis, School of Computer Science, University of Windsor, Ontario, Canada.
• 2: Abdullah, N. and Frost, R. A. 2005. Adjectives: A uniform semantic approach. In Proceedings of Advances in Artificial Intelligence: the 18th Conference of the Canadian Society for Computational Studies of Intelligence (AI'02). B. Kegl and G. Lapalme, Eds. Lecture Notes in Computer Science, vol. 3501. Springer-Verlag, 330--341.
• 3: Ahn, K., Bos, J., Clark, S., Curran, J. R., Dalmas, T., Leidner, J. L., Smillie, M. B., and Webber, B. 2004. Question answering with QED and WEE at TREC-2004. In Proceedings of the 13th Text Retrieval Conference (TREC'04). E. M. Voorhees and L. P. Buckland, Eds. U.S. National Institute of Standards and Technology, (NIST), Gaithesburg, MD.
• 4: Ajdukiewicz, K. 1935. Die syntaktische konnexitat. Studia Philosophica 1, 1--27.
• 5: Andersson, I. and Sodereberg, T. 2003. Spanish morphology implemented in a functional programming language. M.S. thesis, Department of Computing Science Chalmers University of Technology and the University of Gothenburg.
• 6: Androutsopoulos, I., Ritchie, G. D., and Thanisch, P. 1995. Natural language interfaces to databases: An introduction. J. Lang. Engin. 1, 1, 29--81.
• 7: Lex Augusteijn, The Elegant Compiler Generator System, Proceedings of the International Conference WAGA on Attribute Grammars and their Applications, p.238-254, September 19-21, 1990
• 8: Backus, J. W. 1959. The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM conference. In Proceedings of the International Conference on Information Processing, UNESCO. 125--132.
• 9: Baldridge, J. M. and Kruijff, G. M. 2004. Course notes on combinatorial categorial grammar. http://esslli2004.loria.fr/content/readers/51.pdf.
• 10: Bar-Hillel, Y. 1953. A quasi-arithmetical notation for syntactic description. Language 29, 47--58.
• 11: Barker, C. 2002. Continuations and the nature of quantification. Natural Language Seman. 10, 211--242.
• 12: Barker, C. 2004. Continuations in natural language. In Proceedings of the 4th ACM SIGPLAN Continuations Workshop (CW'04), H. Thielecke, Ed. School of Computer Science, University of Birmingham, 1--11.
• 13: Benthem, J. V. 1986. Language in action: categories, lambdas and dynamic logic. Sudies in Logic and the Foundation of Mathematics. D. Reidel Publishing.
• 14: Benthem, J. V. 1987. Categorial grammars and lambda calculus. In Mathematical Logic and its Applications, D. Skordev, Ed. Plenum Press.
• 15: Benthem, J. V. 1991. Language in action: categories, lambdas and dynamic logic. Sudies in Logic and the Foundation of Mathematics, vol. 30. North-Holland.
• 16: Blackburn, P. and Bos, J. 2005. Representation and Inference for Natural Language. A First Course in Computational Semantics. CSLI Publications, Stanford University.
• 17: Patrick Blackburn , Marc Dymetman , Alain Lecomte , Aarne Ranta , Christian Retoré , Eric Villemonte de la Clergerie, Logical Aspects of Computational Linguistics: An Introduction, Selected papers from the First International Conference on Logical Aspects of Computational Linguistics, p.1-20, September 23-25, 1996
• 18: Bogavac, L. 2004. Functional morphology for Russian. M.S. thesis, Department of Computing Science, Chalmers University of Technology and the University of Gothenburg.
• 19: Boszahin, C. 1997. Combinatory logic and natural language parsing. Elektrik, Turkish J. of EE and CS 5, 3, 347--357.
• 20: Bringet, B. 2005. Embedded grammars. M.S. thesis, Department of Computer Science and Engineering, Chalmers University of Technology and Gothenburg University.
• 21: T. H. Brus , C. J. D. van Eekelen , M. O. van Leer , M. J. Plasmeijer, CLEAN: A language for functional graph rewriting, Proc. of a conference on Functional programming languages and computer architecture, p.364-384, October 1987, Portland, Oregon, United States
• 22: Burge, W. H. 1975. Recursive Programming Techniques. Addison-Wesley Publishing Co., Reading, MA.
• 23: Burke, D. A. and Johannisson, K. 2005. Translating formal software specifications to natural language/a grammar based approach. In Proceedings of Logical Aspects of Computational Linguistics (LACL'05), P. Blace, E. Stabler, J. Busquets, and R. Moot, Eds. Lecture Notes in Artificial Intelligence, vol. 3402. Springer-Verlag, 52--66.
• 24: Callaghan, P. C. 1998. An evaluation of LOLITA and related natural language processing systems. Ph.D. thesis, Department of Computer Science, University of Durham.
• 25: Callaghan, P. C. 2005. Generalized LR parsing. In The Happy User Guide (Chap. 3). Simon Marlow.
• 26: Bob Carpenter, Type-logical semantics, MIT Press, Cambridge, MA, 1998
• 27: Chomsky, N. 1957. Syntactic Structures. Mouton de Gruyter, The Hague.
• 28: Constantino, M. 1999. IE-Expert: Integrating natural language processing and expert systems techniques for real-time equity derivatives trading. J. Computat. Intell. Finance 7, 2, 34--52.
• 29: Copestake, A. 2005. Natural language processing. Lecture Notes, Computer Laboratory, University of Cambridge.
• 30: Curry, H. and Feys, R. 1958. Combinatory logic. Studies in Logic, vol. 1. North Holland.
• 31: Dalmas, T. 2004. Wee/QAAM Manual. School of Informatics, University of Edinburgh.
• 32: Dowty, D. 1979. Word Meaning and Montague Grammar. D. Reidel Publishing Co.
• 33: Dowty, D. R., Wall, R. E., and Peters, S. 1981. Introduction to Montague Semantics. D. Reidel Publishing Co.
• 34: Marc Dymetman , Veronika Lux , Aarne Ranta, XML and multilingual document authoring: convergent trends, Proceedings of the 18th conference on Computational linguistics, p.243-249, July 31-August 04, 2000, Saarbrücken, Germany [doi>10.3115/990820.990856]
• 35: Jan Van Eijck, Incremental Dynamics, Journal of Logic, Language and Information, v.10 n.3, p.319-351, Summer 2001 [doi>10.1023/A:1011251627260 ]
• 36: Eijck, J. V. 2003. Parser combinators for extraction. In Proceedings of the 14th Amsterdam Colloquium, P. Dekker and R. van Rooy, Eds. 99--104.
• 37: Eijck, J. V. 2004. Deductive parsing in haskell. Unpublished paper Uil-OTS/CWI/ILLC, Amsterdam and Utrecht.
• 38: Eijck, J. V. and Nouwen, R. 2002. Quantification and reference in incremental processing. Unpublished paper, UiL-OTS/CWI/ILLC, Amsterdam and Utrecht.
• 39: Fairburn, J. 1986. Making form follow function: An exercise in functional programming style. Tech. rep. 89, Computer Laboratory, University of Cambridge.
• 40: Fernandes, J. 2004. Generalized LR parsing in Haskell. Tech. rep. DI-PURe-04.11.01, Departamento de Informatica, da Universidade do Minho, Portugal.
• 41: Fernandez, M. 1995. Spanish generation in the NL system LOLITA. M.S. thesis, Department of Computer Science, University of Durham.
• 42: Jeroen Fokker, Functional Parsers, Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques-Tutorial Text, p.1-23, May 24-30, 1995
• 43: Bryan Ford, Packrat parsing:: simple, powerful, lazy, linear time, functional pearl, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.36-47, October 04-06, 2002, Pittsburgh, PA, USA
• 44: Forsberg, M. 2004. Applications of functional programming in processing formal and natural languages. Licentiate thesis, Department of Computer Science and Engineering. Chalmers University of Technology and Gothenburg University.
• 45: Markus Forsberg , Aarne Ranta, Functional morphology, Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, September 19-21, 2004, Snow Bird, UT, USA
• 46: Frank, A. U. 2001. Tiers of ontology and consistency constraints in geographical information systems. Int. J. Geograph. Inform. Science 15, 7, 667--678.
• 47: R. A. Frost, Constructing programs as executable attribute grammars, The Computer Journal, v.35 n.4, p.376-389, Aug. 1992 [doi>10.1093/comjnl/35.4.376]
• 48: R. A. Frost, Guarded attribute grammars, Software—Practice & Experience, v.23 n.10, p.1139-1156, Oct. 1993 [doi>10.1002/spe.4380231006]
• 49: Richard A. Frost, W/AGE: The Windsor Attribute Grammar Programming Environment, Proceedings of the IEEE 2002 Symposia on Human Centric Computing Languages and Environments (HCC'02), p.96, September 03-06, 2002
• 50: Frost, R. A. 2003. Monadic memoization: Towards correctness-preserving reduction of search. In Proceedings of Advances in Artificial Intelligence: 16th Conference of the Canadian Society for Computational Studies of Intelligence (AI'03), Y. Xiang and B. Chaib-draa, Eds. Lecture Notes in Artificial Intelligence, vol. 2671. Springer-Verlag, 66--80.
• 51: Richard A. Frost, Call for a public-domain SpeechWeb, Communications of the ACM, v.48 n.11, p.45-49, November 2005 [doi>10.1145/1096000.1096003]
• 52: Frost, R. A. 2006. Functional pearl; polymorphism and the meaning of transitive verbs. Tech. rep. 06-006, School of Computer Science, University of Windsor, Ontario, Canada.
• 53: Richard A. Frost , Pierre Boulos, An Efficient Compositional Semantics for Natural-Language Database Queries with Arbitrarily-Nested Quantification and Negation, Proceedings of the 15th Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence, p.252-267, May 27-29, 2002
• 54: Richard A. Frost , Rahmatullah Hafiz, A new top-down parsing algorithm to accommodate ambiguity and left recursion in polynomial time, ACM SIGPLAN Notices, v.41 n.5, May 2006 [doi>10.1145/1149982.1149988]
• 55: Frost, R. A., Hafiz, R., and Callaghan, P. 2006. A general top-down parsing algorithm, accommodating ambiguity and left recursion in polynomial time. Tech. rep. 06-022, School of Computer Science, University of Windsor, Canada.
• 56: R. Frost , J. Launchbury, Constructing natural language interpreters in a lazy functional language, The Computer Journal, v.32 n.2, p.108-121, April 1989 [doi>10.1093/comjnl/32.2.108]
• 57: Richard A. Frost , Barbara Szydlowski, Memoizing purely functional top-down backtracking language processors, Science of Computer Programming, v.27 n.3, p.263-288, Nov. 1996 [doi>10.1016/0167-6423(96)00014-7 ]
• 58: Garigliano, R., Morgan, R., and Smith, M. 1992. LOLITA: Progress report 1. Tech. rep. 12/92, Department of Computer Science. University of Durham.
• 59: Garigliano, R., Morgan, R., and Smith, M. 1993. The LOLITA system as a contents scanning tool. In Proceedings of the 13th International Conference on Artificial Intelligence, Expert Systems and Natural Language Processing. Avignon, France.
• 60: Jean-Yves Girard , Paul Taylor , Yves Lafont, Proofs and types, Cambridge University Press, New York, NY, 1989
• 61: Dick Grune , Ceriel J. H. Jacobs, Parsing techniques: a practical guide, Ellis Horwood, Upper Saddle River, NJ, 1990
• 62: Reiner Hähnle , Kristofer Johannisson , Aarne Ranta, An Authoring Tool for Informal and Formal Requirements Specifications, Proceedings of the 5th International Conference on Fundamental Approaches to Software Engineering, p.233-248, April 08-12, 2002
• 63: Hallgreen, T. and Ranta, A. 2000. An extensible proof text editor. In Proceedings of (LPAR'00). M. Parigot and A. Voronkov, Eds. Lecture Notes in Artificial Intelligence, vol. 1955. Springer-Verlag, 70--84.
• 64: Heitz, J. 1996. An investigation into figurative language in the LOLITA NLP system. M.S. thesis, Department of Computer Science, University of Durham.
• 65: Hendriks, H. 1993. Studied flexibility: Categories and types in syntax and semantics. Ph.D. thesis, Universiteit van Amsterdam.
• 66: Hill, S. 1996. Combinators for parsing expressions. J. Funct. Program. 6, 3, 445--463.
• 67: Erhard W. Hinrichs, Tense quantifiers, and contexts, Computational Linguistics, v.14 n.2, June 1988
• 68: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 69: Hudak, P., Peterson, J., and Fasel, J. 2000. A gentle introduction to Haskell. www.Haskell.org.
• 70: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 71: Gérard P. Huet, Zen and the Art of Symbolic Computing: Light and Fast Applicative Algorithms for Computational Linguistics, Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages, p.17-18, January 13-14, 2003
• 72: J. Hughes, Why functional programming matters, The Computer Journal, v.32 n.2, p.98-107, April 1989 [doi>10.1093/comjnl/32.2.98]
• 73: John Hughes, Generalising monads to arrows, Science of Computer Programming, v.37 n.1-3, p.67-111, May 2000 [doi>10.1016/S0167-6423(99)00023-4 ]
• 74: Hutton, G. 1992. Higher-order functions for parsing. J. Funct. Program. 2, 3, 323--343.
• 75: Graham Hutton , Erik Meijer, Monadic parsing in Haskell, Journal of Functional Programming, v.8 n.4, p.437-444, July 1998 [doi>10.1017/S0956796898003050]
• 76: Maria Lucja Iwanska, A general semantic model of negation in natural language: representation and inference, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 77: Johan Jeuring , S. Doaitse Swierstra, Bottom-up Grammar Analysis - A Functional Formulation, Proceedings of the 5th European Symposium on Programming: Programming Languages and Systems, p.317-332, April 11-13, 1994
• 78: Johannisson, K. 2005. Formal and informal software specifications. Ph.D. thesis, Department of Computer Science and Engineering. Chalmers University of Technology and Gothenburg University.
• 79: Mark Johnson, Memoization in top-down parsing, Computational Linguistics, v.21 n.3, September 1995
• 80: Thomas Johnsson, Attribute grammars as a functional programming paradigm, Proc. of a conference on Functional programming languages and computer architecture, p.154-173, October 1987, Portland, Oregon, United States
• 81: Jones, M. P., Hudak, P., and Shuamyan, S. 1995. Using types to parse natural language. In Proceedings of the Glasgow Workshop on Functional Programming. Workshops in Computer Science Series. (IFIP), Springer-Verlag.
• 82: Khegai, J., Nordstrm, B., and Ranta, A. 2003. Multilingual syntax editing in GF. In Proceedings of the 4th International Conference on Intelligent Text Processing and Computational Linguistics (CICLing'03), A. F. Gelbukh, Ed. Lecture Notes in Computer Science, vol. 2588. Springer-Verlag, 453--464.
• 83: Khegai, J. and Ranta, A. 2004. Building and using a Russian resource grammar in GF. In Proceedings of the 5th International Conference on Intelligent Text Processing and Computational Linguistics (CICLing'04), A. F. Gelbukh, Ed. Lecture Notes in Computer Science, vol. 2945. Springer-Verlag, 38--41.
• 84: Pieter W. M. Koopman , Marinus J. Plasmeijer, Efficient Combinator Parsers, Selected Papers from the 10th International Workshop on 10th International Workshop, p.120-136, September 09-11, 1998
• 85: Korte, L. 2004. Deep types for categorial grammar: A side effect analysis. In Proceedings of TAAL Postgraduate Conference. Edinburgh University.
• 86: Kudlek, M., Martin-Vide, C., Mateescu, A., and Mitrana, V. 2003. Contexts and the concept of mild-context-sensitivity. Linguist. Philos. 26, 703--725.
• 87: Werner Kuhn, Modeling the Semantics of Geographic Categories through Conceptual Integration, Proceedings of the Second International Conference on Geographic Information Science, p.108-118, September 25-28, 2002
• 88: Susumu Kuno, The predictive analyzer and a path elimination technique, Communications of the ACM, v.8 n.7, p.453-462, July 1965 [doi>10.1145/364995.365689]
• 89: Lambek, J. 1958. The mathematics of sentence structure. Amer. Mathemat. Month. 65, 154--170.
• 90: Lapalme, G. and Lavier, F. 1990. Using a functional language for parsing and semantic processing. Tech. rep. 715a, Departement d'informatique et recherche operationelle, Universite de Montreal.
• 91: Lapalme, G. and Lavier, F. 1993. Using a functional language for parsing and semantic processing. Computat. Intell. 9, 111--131.
• 92: Rene Leermakers, The Functional Treatment of Parsing, Kluwer Academic Publishers, Norwell, MA, 1993
• 93: Leijen, D. and Meijer, E. 2001. Parsec: Direct style monadic parser combinators for the real world. Tech. rep. UU-CS-2001-35, Department of Computer Science, University of Utrecht.
• 94: Lickman, P. 1995. Parsing with fixed points. M.S. thesis, University of Cambridge.
• 95: Ljunglof, P. 2002a. Functional programming and NLP. Tech. rep., Department of Computer Science, Chalmers University.
• 96: Ljunglof, P. 2002b. Pure functional parsing-an advanced tutorial. Licentiate thesis, Department of Computing Science, University of Gothenburg.
• 97: Peter Ljunglöf, Functional chart parsing of context-free grammars, Journal of Functional Programming, v.14 n.6, p.669-680, November 2004 [doi>10.1017/S0956796804005106]
• 98: Hans-Wolfgang Loidl , Richard G. Morgan , Philip W. Trinder , Sanjay Poria , Chris Cooper , Simon L. Peyton Jones , Roberto Garigliano, Parallelising a Large Functional Program or: Keeping LOLITA Busy, Selected Papers from the 9th International Workshop on Implementation of Functional Languages, p.198-213, September 10-12, 1997
• 99: Derek Long , Roberto Garigliano, Reasoning by analogy and causality: a model and application, Ellis Horwood, Upper Saddle River, NJ, 1994
• 100: Marlow, S. 2005. The Happy User Guide. http://www.Haskell.org/happy/doc/html/index.html.
• 101: Medlock, B. 2002. A tool for generalized LR parsing in Haskell. Single honours C.S. project report, Department of Computer Science, University of Durham.
• 102: Farid Meziane , Elizabeth Métais, Natural Language Processing and Information Systems: 9th International Conference on Applications of Natural Languages to Information Systems, NLDB 2004, ... (Lecture Notes in Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 103: Montague, R. 1970. Universal grammar. Theoria 36, 373--398. (Reprinted in Thomason 1974, 222--246.)
• 104: Montague, R. 1973. The proper treatment of quantification in ordinary English. In Approaches to Natural Language, K. J. J. Hintikka, J. M. E. Moravcsik, and P. Suppes, Eds. D. Reidel Publishing Co., 221--242.
• 105: Moortgat, M. 1988. Categorial Investigations. Logical and Linguistic Aspects of the Lambek Calculus. Foris Publications, Dordrecht.
• 106: Richard Morgan , Roberto Garigliano , Paul Callaghan , Sanjay Poria , Mark Smith , Chris Cooper, University of Durham: description of the LOLITA system as used in MUC-6, Proceedings of the 6th conference on Message understanding, November 06-08, 1995, Columbia, Maryland [doi>10.3115/1072399.1072408]
• 107: Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
• 108: Rishiyur S. Nikhil, A Multithreaded Implementation of Id using P-RISC Graphs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.390-405, August 12-14, 1993
• 109: Peter Norvig, Techniques for automatic memoization with applications to context-free parsing, Computational Linguistics, v.17 n.1, March 1991
• 110: Jukka Paakki, Attribute grammar paradigms—a high-level methodology in language implementation, ACM Computing Surveys (CSUR), v.27 n.2, p.196-255, June 1995 [doi>10.1145/210376.197409]
• 111: Pace, G. 2004. Monadic compositional parsing with context using maltese as a case study. In Proceedings of the Computer Science Annual Workshop (CSAW'04), University of Malta, G. Pace and J. Cordina, Eds. 60--70.
• 112: Panitz, S. E. 1996. Termination proofs for a lazy functional language by abstract reduction. Tech. rep. 06, J. W. Goethe-Universitat. citeseer.nj.nec.com/panitz96termination.html.
• 113: Partee, B. H. 1975. Montague grammar and transformational grammar. Linguis. Inquiry 6, 2, 203--300.
• 114: Partee, B. H., Ed. 1976. Montague Grammar. Academic Press, New York, NY.
• 115: Partee, B. H. 2001. Montague Grammar. In International Encyclopedia of the Social and Behavioral Sciences, N. J. Smelser and P. B. Baltes, Eds. Elsevier.
• 116: Partee, B. H. and Hendricks, L. W. 1997. Montague Grammar. In Handbook of Logic and Language, J. van Benthem and A. ter Meulen, Eds. Elsevier, 5--91.
• 117: Partridge, A. and Wright, D. 1996. Predictive parser combinators need four values to report errors. J. Funct. Program. 6, 2, 355--364.
• 118: Pembecci, I. 1995. A combinator parser for the morphological analysis of Turkish. Senior project report, Department of Computer Engineering, Middle East Technical University, Ankara.
• 119: Fernando C. N. Pereira, Categorial semantics and scoping, Computational Linguistics, v.16 n.1, p.1-10, March 1990
• 120: Peyton-Jones, S. 2003. The Haskell 98 language. J. Funct. Program. 13, 1, 0--255.
• 121: Aarne Ranta, Type-theoretical grammar, Oxford University Press, Oxford, 1995
• 122: Ranta, A. 1995. Type-theoretical interpretation and generalization of phrase structure grammar. Bull. of the IGPL 3, 2, 319--342.
• 123: Ranta, A. 2001. 1+n representations of Italian morphology. Essays dedicated to Jan von Plato on the occasion of his 50th birthday.
• 124: Aarne Ranta, Grammatical Framework, Journal of Functional Programming, v.14 n.2, p.145-189, March 2004 [doi>10.1017/S0956796803004738]
• 125: Aarne Ranta , Robin Cooper, Dialogue Systems as Proof Editors, Journal of Logic, Language and Information, v.13 n.2, p.225-240, Spring 2004 [doi>10.1023/B:JLLI.0000024736.34644.48]
• 126: Chris Reed , Derek Long , Maria Fox , Max Garagnani, Persuasion as a Form of Inter-Agent Negotiation, Revised Papers from the Second Australian Workshop on Distributed Artificial Intelligence: Multi-Agent Systems: Methodologies and Applications, p.120-136, August 27, 1996
• 127: Emmanuel Roche , Yves Shabes, Finite-State Language Processing, MIT Press, Cambridge, MA, 1997
• 128: Rose, T., Elworthy, D., Kotche, A., Clare, A., and Tsonis, P. 2000. ANVIL: A system for the retrieval of captioned images using NLP techniques. In Proceedings of Challenge of Image Retrieval (CIR'00). J. P. Eakins and P. G. B. Enser, Eds. University of Brighton, UK.
• 129: Roy, M. 2005. Extending a set-theoretic implementation of Montague Semantics to accommodate n-ary trnasitive verbs. M.S. thesis, School of Computer Science, University of Windsor, Ontario, Canada.
• 130: Roy, M. and Frost, R. 2004. Extending Montague Sematics for use in natural language database-query processing. In Proceedings of Advances in Artificial Intelligence: The 17th Conference of the Canadian Society for Computational Studies of Intelligences (AI'04). A. Tawfik and S. Goodwin, Eds. Lecture Notes in Computer Science, vol. 3060. Springer-Verlag, 567--568.
• 131: Walter J. Savitch, A formal model for context-free languages augmented with reduplication, Computational Linguistics, v.15 n.4, p.250-261, December 1989
• 132: Shan, C. 2001a. Monads for natural language semantics. In Proceedings of the 13th European Summer School in Logic, Language and Information.Student Session (ESSLLI'01), K. Striegnitz, Ed. Helsinki, Finland, 285--298.
• 133: Shan, C. 2001b. A variable-free dynamic semantics. In Proceedings of the 13th Amsterdam Colloquium, R. van Rooy and M. Stokhof, Eds. Institute for Logic, Language and Computation, Universiteit van Amsterdam, 204--209.
• 134: Shan, C. 2002. A continuation semantics of interrogatives that accounts for baker's ambiguity. In Semantics and Linguistic Theory (SALT XII). B. Jackson, Ed. Cornell University Press, 246--265.
• 135: Shan, C. 2003. Linguistic side effects. In Proceedings of the 18th Annual IEEE Symposium on Logic and Computer Science (LICS'03) Workshop on Logic and Computational Linguistics. L. Libkin and G. Penn, Eds. Ottawa, Canada.
• 136: Shan, C. and Barker, C. 2004. Explaining crossover and superiority as left-to-right evaluation. In Worshop on Semantic Approaches to Binding Theory (ESSLLI'04), the 16th European Summer School in Logic, Language and Information. E. Keenan and P. Schlenker, Eds. Nancy, France.
• 137: Shaumyan, S. 1977. Applicational Grammar as a Semantic Theory of Natural Language. Edinburgh University Press.
• 138: Sebastian Shaumyan , Paul Hudak, Linguistic, Philosophical, and Pragmatic Aspects of Type-Directed Natural Language, Selected papers from the Second International Conference on Logical Aspects of Computational Linguistics, p.70-91, September 22-24, 1997
• 139: Sebastian Shaumyan , Frédérique Segond, Long-distance dependencies and Applicative Universal Grammar, Proceedings of the 15th conference on Computational linguistics, August 05-09, 1994, Kyoto, Japan [doi>10.3115/991250.991285]
• 140: Shieber, S. M. 1985. Evidence against the context-freeness of natural language. Linguist. Philos. 8, 333--343.
• 141: Shiel, B. A. 1976. Observations on context-free parsing. Tech. rep. TR 12-76, Center for Research in Computing Technology, Aiken Computational Laboratory, Harvard University.
• 142: Simon Shiu , Zhaohui Luo , Roberto Garigliano, Type Theoretic Semantics for SemNet, Proceedings of the International Conference on Formal and Applied Practical Reasoning, p.582-595, June 03-07, 1996
• 143: Shiu, S. K. Y. 1997. Type theoretic semantics for semantic networks: An application to natural language engineering. Ph.D. thesis, Department of Computer Science, University of Durham.
• 144: S. Short , S. Shiu , R. Garigliano, Distributedness and non-linearity of LOLITA's semantic network, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark [doi>10.3115/992628.992704]
• 145: Smith, M. H. 1996. Natural language generation in the LOLITA system: An engineering approach. Ph.D. thesis, Department of Computer Science, University of Durham.
• 146: Smith, M. H., Garigliano, R., and Morgan, R. 1994. Generation in the LOLITA system: An engineering approach. In Proceedings of the 16th International Natural Language Generation Workshop. 241--244.
• 147: Mark Steedman, Type-raising and directionality in combinatory grammar, Proceedings of the 29th annual meeting on Association for Computational Linguistics, p.71-78, June 18-21, 1991, Berkeley, California [doi>10.3115/981344.981354]
• 148: Steedman, M. 1996. A very short introduction to CCG. Unpublished paper. http://www.coqsci.ed.ac.uk/steedman/paper.html
• 149: Mark Steedman, Alternating quantifier scope in CCG, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.301-308, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034728]
• 150: Steedman, M. and Baldridge, J. 2003. Combinatory categorial grammar. Unpublished tutorial, School of Informatics, Edinburgh University. ftp://ftp.cogsci.ed.ac.uk/pub/steedman/ccg/manifesto.pdf.
• 151: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 152: S. Doaitse Swierstra , Luc Duponcheel, Deterministic, Error-Correcting Combinator Parsers, Advanced Functional Programming, Second International School-Tutorial Text, p.184-207, August 26-30, 1996
• 153: Sypniewski, B. P. 1999. An introduction to applicative universal grammar. Unpublished paper. http://elvis.rowan.edu/bps/ling/introAUG.pdf.
• 154: Barbara Szydlowski, Complexity analysis and monadic specification of memoized functional parsers, University of Windsor, University of Windsor, Ontario, 1997
• 155: Thomason, R. H. 1974. Formal Philosophy: Selected Papers of Richard Montague. Yale University Press, New Haven CT.
• 156: Masaru Tomita, Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, Kluwer Academic Publishers, Norwell, MA, 1985
• 157: Turner, D. A. 1979. A new implementation technique for applicative languages. Softw. Pract. Exper. 9, 1, 31--49.
• 158: Turner, D. A. 1981. Aspects of the implementation of programming languages. Ph.D. thesis, Oxford University, Oxford, UK.
• 159: D. A. Turner, Miranda: a non-strict functional language with polymorphic types, Proc. of a conference on Functional programming languages and computer architecture, p.1-16, January 1985, Nancy, France
• 160: D Turner, An overview of Miranda, ACM SIGPLAN Notices, v.21 n.12, p.158-166, Dec. 1986 [doi>10.1145/15042.15053]
• 161: Udderborg, G. 1988. A functional parser generator. Licentiate thesis, Chalmers University of Technology, Gothenburg.
• 162: Philip Wadler, How to replace failure by a list of successes, Proc. of a conference on Functional programming languages and computer architecture, p.113-128, January 1985, Nancy, France
• 163: Wadler, P. J. 1989. Special edition on lazy functional programming. Comput. J. 32, 2.
• 164: Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France [doi>10.1145/91556.91592]
• 165: Wadler, P. J. 1994. Tech. rep., http://homepages.inf.ed.ac.uk/wadler/realworld/satelite.html.
• 166: Philip Wadler, Monads for Functional Programming, Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques-Tutorial Text, p.24-52, May 24-30, 1995
• 167: Wang, Y. 1994. An intelligent computer-based tutoring approach for the management of negative transfer. Ph.D. thesis, Department of Computer Science, Durham University.
• 168: Ziff, D. A., Spackman, S. P., and Waclena, K. 1995. Funser: A functional server for textual information retrieval. J. Funct. Program. 5, 3, 317--343.

INDEX TERMS

Primary Classification:
  A. General Literature
  A.1 INTRODUCTORY AND SURVEY

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics; Syntax

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Partial evaluation; Denotational semantics
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive); Parsing

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Natural language

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Natural language interfaces
      I.2.7 Natural Language Processing
          Subjects: Language models; Language parsing and understanding

  J. Computer Applications
  J.5 ARTS AND HUMANITIES
      Subjects: Linguistics

General Terms: