Reconstructing the Evolutionary History of IndoEuropean 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 nontree
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 IndoEuropean languages.
The talk presented a good introduction to answerset programming.
The answerset logic programming is more general than Prolog's
builtin DepthFirst search. For one thing, the answerset semantics
admits more logical programs (because answerset solvers find
solutions where equivalent Prolog programs just loop). For another,
the answerset 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

