Thumbnail
Access Restriction
Subscribed

Author Rossman, Benjamin
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Previous work of the author [Rossman 2008a] showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the $AC^{0}$ formula size of the colored subgraph isomorphism problem. Formally, we show the following: if a first-order sentence Φ of quantifier-rank k is preserved under homomorphisms on finite structures, then it is equivalent on finite structures to an existential-positive sentence Ψ of quantifier-rank $k^{O(1)}.$ Quantitatively, this improves the result of [Rossman 2008a], where the upper bound on the quantifier-rank of Ψ is a non-elementary function of k.
Description Affiliation: University of Toronto (Rossman, Benjamin)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-02-17
Publisher Place New York
Journal ACM SIGLOG News (SIGL)
Volume Number 3
Issue Number 4
Page Count 14
Starting Page 33
Ending Page 46


Open content in new tab

   Open content in new tab
Source: ACM Digital Library