Authors: Skip Jordan and Thomas Zeugmann
Source: Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi'an, China, April 2008, Proceedings , (Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li, Eds.), Lecture Notes in Computer Science 4978, pp. 94-104, Springer 2008.
Abstract. The “richness” of properties that are indistinguishable from first-order properties is investigated. Indistinguishability is a concept of equivalence among properties of combinatorial structures that is appropriate in the context of testability. All formulas in a restricted class of second-order logic are shown to be indistinguishable from first-order formulas. Arbitrarily hard properties, including RE-complete properties, that are indistinguishable from first-order formulas are shown to exist. Implications on the search for a logical characterization of the testable properties are discussed.
©Copyright 2008, Springer