The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
This is a paper about a certain period of the develpoment of model theory upon which the work of A. Ehrenfeucht made an indelible mark. We will pay a special attention to his results about the theories of (Ord,<), (Ord,<,+), and (Ord,<,+,·). Also some of the history of the applications of Ramsey's theorem in model theory will be discussed.
Logic preservation theorems often have the form of a syntax/semantics correspondence. For example, the Los-Tarski theorem asserts that a first-order sentence is preserved by extensions if and only if it is equivalent to an existential sentence. Many of these correspondences break when one restricts attention to finite models. In such a case, one may attempt to find a new semantical characterization...
We compare the expressive power on finite models of two extensions of first order logic L with equality. L(Ct) is formed by adding an operator count x∶ϕ, which builds a term of sort N that counts the number of elements of the finite model satisfying a formula ϕ. Our main result shows that the stronger operator count t(x)∶ϕ, where t(x) is a term of sort N, cannot be expressed in L(Ct). That is, being...
We report a recent Tarski-style semantics for a language which includes the branching quantifiers on which Andrzej Ehrenfeucht made the first breakthrough in 1958. The semantics is equivalent to Henkin's game-theoretic semantics, but unlike Henkin's it is compositional. We use second-order formulas to give a new (and with any luck, more manageable) description of this Tarski-style semantics. Finally...
This article describes the Ehrenfeucht game and its applications in two areas of model theory: definability theory and random model theory. Most of the examples are taken from finite model theory, where the Ehrenfeucht game is one of the most useful tools. Extensions of the Ehrenfeucht game to logics more expressive than first-order logic are described, and applications to definability and random...
It is well-known that in first-order logic, the theory of a binary relation and the theory of a ternary relation are mutually interpretable, i.e., each can be interpreted in the other. We establish the stronger result that they are interpretively isomorphic, i.e., they are mutually interpretable by a pair of interpretations each of which is the inverse of the other.
Vagueness for a long time has been studied by philosophers, logicians and linguists. Recently researchers interested in AI contributed essentially to this area. In this paper we present a new approach to vagueness, called rough set theory. The starting of the theory theory is the assumption that fundamental mechanisms of human reasoning are based on the ability to classify object of interest,...
When Ehrenfeucht introduced his game theoretic characterization of elementary equivalence in 1961, the first application of these “Ehrenfeucht games” was to show that certain ordinals (considered as orderings) are indistinguishable in first-order logic and weak monadic second-order logic. Here we review Shelah's extension of the method, the “composition of monadic theories”, explain it in the example...
A formula from monadic second-order (MSO) logic can be used to specify a binary relation on the set of nodes of a tree. It is proved that, equivalently, such a relation can be computed by a finite-state tree-walking automaton, provided the automaton can test MSO properties of the nodes of the tree. For graphs, if a binary relation on the nodes of a graph can be computed by a finite-state graph-walking...
We introduce a new method of approximating volume (and integrals) for a vast number of geometric bodies defined by boolean combinations of Pfaffian conditions. The method depends on the VC Dimension of the underlying classes of bodies. The resulting approximation algorithms are quite different in spirit from previously known methods, and give randomized solutions even for such seemingly intractable...
A complementation operation on a vertex of a digraph changes all outgoing edges into nonedges, and outgoing nonedges into edges. A similar operation is defined for incoming edges. This defines an equivalence relation where two graphs are equivalent if one can be obtained from the other by a sequence of such operations. We show that given an adjacency-list representation of a digraph G, many fundamental...
The Directed Acyclic Word Graph (DAWG) is a space-efficient data structure to treat and analyze repetitions in a text, especially in DNA genomic sequences. Here, we consider the Compact Directed Acyclic Word Graph of a word. We give the first direct algorithm to construct it. It runs in time linear in the length of the string on a fixed alphabet. Our implementation requires half the memory space used...
We apply recent results on the minimax risk in density estimation to the related problem of pattern classification. The notion of loss we seek to minimize is an information theoretic measure of how well we can predict the classification of future examples, given the classification of previously seen examples. We give an asymptotic characterization of the minimax risk in terms of the metric entropy...
Quasiperiodic strings were defined by Apostolico and Ehrenfeucht [3], as strings which are entirly covered by occurrences of another(shorter) string. This paper surveys a handful of results on the structure and detection of quasiperiodic strings and on related string covers,attempting to simplify and present in a uniform manner the algorithms being surveyed.
We overview some recent developments of the theory of Sturmian words showing that the ’kernel’ of the theory is the combinatorics of the set PER of all finite words ω on the alphabet A={a,b} having two periods p and q which are coprimes and such that |w|=p+q-2. The elements of PER have many surprising structural properties. In particular, the relation Stand=A U PER ab, ba holds, where Stand is the...
A semigroup S is said to have the compactness property, or CP for short, if each system of equations over a finite set of variables has an equivalent finite subsystem, that is, having exactly the same solutions in S. We prove that a completely 0-simple semigroup S satisfies CP if and only if the group G in a Rees matrix representation S=M°(I, G, ∧; P) satisfies this property. Further, a variety of...
Equivalence and rationality problems are shown to be decidable for algebraic series with noncommuting variables having bounded supports. As a tool, Parikh simplifying mappings are defined and studied.
Some shuffle-like operations on infinite (ω-words) are investigated. The operations are introduced using a uniform method based on the notion of an ω-trajectory. We prove an interconnection between associative closure of shuffle on ω-trajectories and periodicity of ω-words. This provides a characterization of the ultimately periodic ω-words. Finally, a remarkable property of the Fibonacci ω-word is...
We state a simple condition on a rational subset X of a free monoid B* for the existence of a sequential function that is a one-to-one mapping of some free monoid A* onto X. As a by-product we obtain new sequential bijections of a free monoid onto another.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.