Lambda the Ultimate

inactiveTopic Evolution of Indo-European Languages using ASP
started 2/17/2003; 4:24:06 AM - last post 2/17/2003; 6:41:16 AM
Ehud Lamm - Evolution of Indo-European Languages using ASP  blueArrow
2/17/2003; 4:24:06 AM (reads: 1327, responses: 1)
Evolution of Indo-European Languages using ASP
Reconstructing the Evolutionary History of Indo-European Languages using Answer Set Programming. Esra Erdem, Vladimir Lifschitz, Luay Nakhleh, and Donald Ringe. PADL'03.

The evolutionary history of languages can be modeled as a tree, called a phylogeny, where the leaves represent the extant languages, the internal vertices represent the ancestral languages, and the edges represent the genetic relations between the languages. Languages not only inherit characteristics from their ancestors but also sometimes borrow them from other languages. Such borrowings can be represented by additional non-tree edges. This paper addresses the problem of computing a small number of additional edges that turn a phylogeny into a "perfect phylogenetic network". To solve this problem, we use answer set programming, which represents a given computational problem as a logic program whose answer sets correspond to solutions. Using the answer set solver SMODELS, with some heuristics and optimization techniques, we have generated a few conjectures regarding the evolution of Indo-European languages.

The talk presented a good introduction to answer-set programming. The answer-set logic programming is more general than Prolog's built-in Depth-First search. For one thing, the answer-set semantics admits more logical programs (because answer-set solvers find solutions where equivalent Prolog programs just loop). For another, the answer-set semantics makes it very easy to keep adding constraints.

The generated conjectures have been subjected to validation by professional linguists. Three conjectures were validated -- one of which wasn't known before.

-- Oleg.

Posted to Logic/Declerative by Ehud Lamm on 2/17/03; 4:32:05 AM

Marc Hamann - Re: Evolution of Indo-European Languages using ASP  blueArrow
2/17/2003; 6:41:16 AM (reads: 523, responses: 0)
While this may have been an interesting demonstration of the ASP method, it is a lousy example of the _successful_ application of the method.

Setting aside the dodginess of language reconstruction in the first place ( a controversial area ), the fact that the vast majority of solutions had to be rejected as "implausible" on problem-external grounds has to make you wonder about the usefulness of the approach.