Applying CLP to machine translation: A Greek case study




CLP, Greek, ambiguity treatement, machine translation, constraint programming, ProLog


In this research we concentrate on how CSP techniques can contribute to computational linguistics. For this purpose, we tested CP techniques on a linguistic problem of polysemy in machine translation. Ambiguity arises almost every time computers try to deal with human language. In information retrieval, the computer often provides information about alternative meanings of the search terms, meanings that we have no interest in. In machine translation, different meanings of an English word may be expressed by very different words in the target language, so it is important to determine which meaning of the English word the author had in mind and this is where a computer fails. Over and over, attempts to use computers to process human language have been frustrated by the computer’s limited ability to deal with polysemy (Miller 2001).

A toy system has been designed for translating between English and Greek. It is based on 6 sentences that, using the same lexicon, can be expanded to slightly more phrases. The translation is based on the results of two parsers — the English and the Greek one. Parsing uses a set of constraints (both semantic and grammatical). The main objective of this research is to evaluate Backtracking as one of CSP algorithms for machine translation. We used PROLOG to write an application because it is the only programming language that supports backtracking and where the choice made by the program can be traced back at every stage.



Association for Logic Programming (community web). Available at: (accessed 15.06.2019). (In English)

Barták, R. (1998) On-line Guide to Constraint Programming. [Online]. Available at: (accessed 15.06.2019). (In English)

Barták, R. On-line Guide to Prolog Programming (tutorial). [Online]. Available at: (accessed 15.06.2019). (In English)

Blackburn P., Bos J., Striegnitz K. Learn Prolog Now! (tutorial). Available at: (accessed 19.07.2019). (In English)

Constraint Programming online (community web). Available at: (accessed 15.06.2019).(In English)


Barták, R. (2001) Constraint propagation and backtracking-based search. A brief introduction to mainstream techniques of constraint satisfaction. Prague: Charles University, 43 p. (In English)

Bratko, I. (2001) PROLOG programming for artificial intelligence. 3rd ed. Harlow: Addison-Wesley, 696 p. (In English)

Dechter, R., Frost, D. (1999) Backtracking algorithms for constraint satisfaction problems. Constraints, 48. [Online]. Available at: (accessed 19.07.2019). (In English)

Freuder, E. C., Carchrae, T., Beck, J. Ch. (2003) Satisfaction guaranteed. Proceedings of the IJCAI-2003 Workshop Configuration, 135 (1–2), pp. 1–6. (In English)

Miller, G. A. (2001) Ambiguous words. iMP Magazine. [Online]. Available at: (accessed 19.07.2019) (In English)

Montanari, U. (1974) Networks of constraints fundamental properties and applications to picture processing. Information Sciences, 7: 95–132. (In English)

Russell, S., Norvig, P. (2002) Artificial intelligence: A modern approach. 2nd ed. New Jersey: Prentice Hall, 1109 p. (In English)

Waltz, D. L. (1975) Understanding line drawings of scenes with shadows. In: Psychology of Computer Vision. New York: McGraw-Hill Publ., pp. 19–91. (In English)

White, Ch. M. (1995) Converting context-free grammars to constraint dependency grammars. A Master of Science thesis (Philology). West Lafayette, Purdue University, 88 p. (In English)





Applied Linguistics