Back to Search Start Over

A Semantic Parsing Algorithm to Solve Linear Ordering Problems

Authors :
Alkhairy, Maha
Homer, Vincent
O'Connor, Brendan
Publication Year :
2025

Abstract

We develop an algorithm to semantically parse linear ordering problems, which require a model to arrange entities using deductive reasoning. Our method takes as input a number of premises and candidate statements, parsing them to a first-order logic of an ordering domain, and then utilizes constraint logic programming to infer the truth of proposed statements about the ordering. Our semantic parser transforms Heim and Kratzer's syntax-based compositional formal semantic rules to a computational algorithm. This transformation involves introducing abstract types and templates based on their rules, and introduces a dynamic component to interpret entities within a contextual framework. Our symbolic system, the Formal Semantic Logic Inferer (FSLI), is applied to answer multiple choice questions in BIG-bench's logical_deduction multiple choice problems, achieving perfect accuracy, compared to 67.06% for the best-performing LLM (GPT-4) and 87.63% for the hybrid system Logic-LM. These promising results demonstrate the benefit of developing a semantic parsing algorithm driven by first-order logic constructs.<br />Comment: 3 figures, 9 pages main paper and 6 pages references and appendix

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2502.08415
Document Type :
Working Paper