Show simple item record

dc.contributor.authorKfoury, A.J.en_US
dc.contributor.authorWymann-Böni, M.en_US
dc.date.accessioned2011-09-12T14:27:46Z
dc.date.available2011-09-12T14:27:46Z
dc.date.issued1993-08
dc.identifier.citationKfoury, A.J.; Wymann-Boeni, M.. "A Characterization of First-Order Definable Subsets on Classes of Finite Total Orders", Technical Report BUCS-1993-009, Computer Science Department, Boston University, August 1993. [Available from: http://hdl.handle.net/2144/1472]
dc.identifier.urihttps://hdl.handle.net/2144/1472
dc.description.abstractWe give an explicit and easy-to-verify characterization for subsets in finite total orders (infinitely many of them in general) to be uniformly definable by a first-order formula. From this characterization we derive immediately that Beth's definability theorem does not hold in any class of finite total orders, as well as that McColm's first conjecture is true for all classes of finite total orders. Another consequence is a natural 0-1 law for definable subsets on finite total orders expressed as a statement about the possible densities of first-order definable subsets.en_US
dc.description.sponsorshipNSF (CCR-9113196), Swiss National Science Foundationen_US
dc.language.isoen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-1993-009
dc.titleA Characterization of First-Order Definable Subsets on Classes of Finite Total Ordersen_US
dc.typeTechnical Reporten_US


This item appears in the following Collection(s)

Show simple item record