Recent zbMATH articles in MSC 03Chttps://zbmath.org/atom/cc/03C2021-06-15T18:09:00+00:00WerkzeugBook review of: J. Golińska-Pilarek (ed.) and M. Zawidzki (ed.), Ewa Orłowska on relational methods in logic and computer science.https://zbmath.org/1460.000192021-06-15T18:09:00+00:00"Rewitzky, Ingrid"https://zbmath.org/authors/?q=ai:rewitzky.ingridReview of [Zbl 1411.03003].Ultrafilters, finite coproducts and locally connected classifying toposes.https://zbmath.org/1460.030082021-06-15T18:09:00+00:00"Garner, Richard"https://zbmath.org/authors/?q=ai:garner.richardThe principal objective in this paper is to describe a single category-theoretic result from which the notions of ultrafilter, ultrapower, tensor product of ultrafilters and Blass' category $\mathcal{UF}$ of ultrafilters, together with their interrelations, all flow naturally, and which, with only a little more effort, is able to speak towards the applications of ultrafilters in model theory. The first main result (Theorem 13 and Corollary 14) goes as follows.
Theorem.
The category $\mathsf{FC}(\mathcal{S}\mathsf{et},\mathcal{S}\mathsf{et})$ of finite-coproduct-preserving endofunctors of $\mathcal{S}\mathsf{et}$ is equivalent to the category $\left[ \mathcal{UF},\mathcal{S}\mathsf{et}\right] $ of functors on Blass' category of ultrafilters $\mathcal{UF}$. Under this equivalence, the ultrapower functor $(-)^{\mathcal{U}}$ corresponds to the representable functor at the ultrafilter $\mathcal{U}$.
The above result, claiming that once we know what a finite-coproduct-preserving endofunctor of $\mathcal{S}\mathsf{et}$ is, everything else is forced, is built on \textit{R. Börger}'s characterization [Seminarber. Fachbereich Math., Fernuniv. 6, 173--176 (1980; Zbl 0443.18005)] of the functor
\[
\beta:\mathcal{S}\mathsf{et}\rightarrow\mathcal{S}\mathsf{et}
\]
sending a set $X$ to its set of ultrafilters as the terminal finite-coproduct-preserving endofunctor of $\mathcal{S}\mathsf{et}$. One thing that this theorem does not capture is the notion of ultraproduct, for which the second main result (Theorem 22) is obtained as the following generalization of the above theorem now dealing with ultrafilters on objects of an \textit{extensive} category $\mathcal{C}$ [\textit{A. Carboni} et al., J. Pure Appl. Algebra 84, No. 2, 145--158 (1993; Zbl 0784.18001)].
Theorem.
Let $\mathcal{C}$ be extensive. The category $\mathsf{FC}(\mathcal{C},\mathcal{S}\mathsf{et})$ of finite-coproduct-preserving functors from $\mathcal{C}$ to $\mathcal{S}\mathsf{et}$ is equivalent to the functor category $\left[ \mathcal{UF}_{\mathcal{C}},\mathcal{S}\mathsf{et}\right] $, where ultrafilters on the Boolean algebra give rise to a category $\mathcal{UF}_{\mathcal{C}}$ as a generalization of Blass' $\mathcal{UF}$.
Ultraproducts are to be recaptured from this theorem by taking
\[
\mathcal{C}=\mathcal{S}\mathsf{et}^{X}
\]
in which we have an equivalence
\[
\left[ \mathcal{UF}_{\mathcal{S}\mathsf{et}^{X}},\mathcal{S}\mathsf{et}\right] \simeq\mathsf{FC}(\mathcal{S}\mathsf{et}^{X},\mathcal{S}\mathsf{et})
\]
so that the ultraproduct functors
\[
\Pi_{\mathcal{U}}:\mathcal{S}\mathsf{et}^{X}\rightarrow\mathcal{S}\mathsf{et}
\]
Taking $\mathcal{C}$ to be the classifying Boolean pretopos of a theory $\mathbb{T}$ of classical first-order logic, ultrafilters on $A\in \mathcal{C}$ correspond to model-theoretic types in context $A$, which allows of reconstructing a categorical treatment in [\textit{M. Makkai}, Lect. Notes Math. 859, 157--201 (1981; Zbl 0527.03042)].
The third main result (Theorem 26) as a generalization of the first main result obtained by varying not only the domain category but also the codomain category goes as follows.
Theorem.
Let $\mathcal{C}$ be extensive and $\mathcal{E}$ a locally connected Grothendieck topos $\partial$. The category $\mathsf{FC}(\mathcal{C},\mathcal{E})$ of finite-coproduct-preserving functors from $\mathcal{C}$ to $\mathcal{E}$ is equivalent to the functor category $\left[ \mathcal{UF}_{\mathcal{C}},\mathcal{E}\right] $.
This theorem allows of reconstructing the indexed sum of ultrafilters by remarking that, for any sets $X$ and $Y$, we have an equivalence
\[
\left[ \mathcal{UF}_{\mathcal{S}\mathsf{et}^{X}},\mathcal{S}\mathsf{et}^{Y}\right] \simeq\mathsf{FC}(\mathcal{S}\mathsf{et}^{X},\mathcal{S}\mathsf{et}^{Y})
\]
and defining a \textit{generalized ultraproduct} functor
\[
\mathcal{S}\mathsf{et}^{X}\rightarrow\mathcal{S}\mathsf{et}^{Y}
\]
which corresponds to a pointwise representable functor
\[
\mathcal{UF}_{\mathcal{S}\mathsf{et}^{X}}\rightarrow\mathcal{S}\mathsf{et}^{Y}
\]
to be represented as an \textit{ultraspan}. The author has the idea of relating Makkai's \textit{ultracategories} [\textit{M. Makkai}, Adv. Math. 65, 97--170 (1987; Zbl 0649.03050); in: Proceedings of the Herbrand Symposium. Logic Colloquium '81, held in Marseille, France, July 1981. Amsterdam - New York - Oxford: North-Holland Publishing Company. 217--232 (1982; Zbl 0522.03006)] to the theorem via the machinery of \textit{enriched categories} [\textit{R. F. C. Walters}, Cah. Topologie Géom. Différ. Catégoriques 22, 283--286 (1981; Zbl 0495.18009); \textit{G. M. Kelly}, Basic concepts of enriched category theory. Cambridge etc.: Cambridge University Press (1982; Zbl 0478.18005)], whose full development is relegated to a subsequent paper.
The final main result (Theorem 42) constructs the \textit{locally connected classifying topos} of a suitable pretopos $\mathcal{C}$, the construction being similar to the \textit{topos of types} [Makkai, 1981, loc. cit.; \textit{A. M. Pitts}, J. Pure Appl. Algebra 29, 313--326 (1983; Zbl 0521.03051)] in that it provides a first-order analogue to the operation of canonical extension [\textit{B. Jónsson} and \textit{A. Tarski}, Am. J. Math. 73, 891--939 (1951; Zbl 0045.31505);\textit{B. Jónsson} and \textit{A. Tarski}, Am. J. Math. 74, 127--162 (1952; Zbl 0045.31601); \textit{M. Gehrke} and \textit{B. Jónsson}, Math. Japon. 40, No. 2, 207--215 (1994; Zbl 0855.06009)] on propositional theories.
Theorem.
Let $\mathcal{C}$ be a small De Morgan pretopos. The topos $\mathcal{S}\mathsf{h}(\mathcal{UF}_{\mathcal{C}})$ is a locally connected classifying topos for $\mathcal{C}$ and is itself De Morgan.
Reviewer: Hirokazu Nishimura (Tsukuba)Imaginaries, invariant types and pseudo \(p\)-adically closed fields.https://zbmath.org/1460.030102021-06-15T18:09:00+00:00"Montenegro, Samaria"https://zbmath.org/authors/?q=ai:montenegro.samaria"Rideau-Kikuchi, Silvain"https://zbmath.org/authors/?q=ai:rideau-kikuchi.silvainUsing results from their respective previous work (see the list of references appended to this review), the authors show elimination of imaginaries for bounded pseudo \(p\)-adically closed fields in a natural language. Their proof does not use elimination of imaginaries for \(p\)-adically closed fields.
From the Introduction : ``[\dots] In recent work of [\textit{E. Hrushovski}, in: Valuation theory in interaction. Proceedings of the 2nd international conference and workshop on valuation theory, Segovia and El Escorial, Spain, July 18--29, 2011. Zürich: European Mathematical Society (EMS). 297--319 (2014; Zbl 1401.03062)] on the elimination of imaginaries in algebraically closed valued fields, the focus is shifted to the local question of finding smallest sets of definition for definable types -- and proving that there are enough definable types to deduce elimination of imaginaries. But there are many structures of interest, among which the field of \(p\)-adic numbers, where there are too few definable types for this local approach to work. It is therefore tempting to work with invariant types instead. [\dots] In this paper, we choose to focus on a class of tractable invariant types: those that are arbitrarily close to definable types; the set D(M/A) of Definition 1.1. The first part of this paper consists in providing the tools for an approach to elimination of imaginaries based on these definably approximable types.''
In the second part of the paper, the authors apply their tools of the first half to bounded pseudo \(p\)-adically closed fields. A field is bounded if it has only finitely many finite extensions of each degree. A field \(K\) of characterisitc zero is pseudo \(p\)-adically closed if it has the property that each non-empty absolutely irreducible algebraic variety defined over \(K\) which has a simple point rational over each of the \(p\)-adically closed extensions of \(K\), has a point rational over \(K\). A \(p\)-adically closed field has a unique \(p\)-adic valuation, and it is definable. A bounded pseudo \(p\)-adically closed fields has only finitely many \(p\)-adic valuations, each of which is definable with parameters. The authors are able to show that these valuations are sufficiently orthogonal so that elimination of imaginaries can be obtained by adding essentially not much more than the ``usual'' geometric sorts, used for \(p\)-adically closed fields, for each of the finitely many \(p\)-adic valuations separately.
Note that the authors also correct a small gap in a lemma from [\textit{S. Montenegro}, Ann. Pure Appl. Logic 168, No. 10, 1866--1877 (2017; Zbl 1422.03064)], for elimination of imaginaries for pseudo real closed fields.
Reviewer: Luc Bélair (Montréal)The motivic Thom-Sebastiani theorem for regular and formal functions.https://zbmath.org/1460.140372021-06-15T18:09:00+00:00"Lê, Quy Thuong"https://zbmath.org/authors/?q=ai:le.quy-thuongThis article proposes a new proof of the Thom-Sebastiani theorem for motivic Milnor fibres in the formal setting.
Let \(k\) be an algebraically closed field of characteristic 0. The Grothendieck group \(K_0(\mathrm{Var}_k)\) is an abelian group generated by isomorphism classes of \(k\)-varieties subject to the relation \(X = Y + X \setminus Y\) for all \(Y\) Zariski closed in \(X\). It also has a ring structure induced by the Cartesian product. Let \(\mu_m\) be the group of \(m\)-th roots of unity; a \(\mu_m\) action on a variety \(X\) is called \emph{good} if each orbit is contained in an affine subvariety. The projective system of natural homomorphisms \(\mu_{mn} \to \mu_n\) has a limit \(\hat \mu\) and \(\hat \mu\)-action on a variety is called \emph{good} if it factors through a good \(\mu_m\)-action for some \(m\). The \(\hat \mu\)-equivariant Grothendieck group \(K^{\hat \mu}_0(\mathrm{Var}_k)\) consists of formal combinations of varieties with good \(\hat \mu\)-action and is defined similarly to \(K_0(\mathrm{Var}_k)\). Let \(\mathbb{L}\) be the class of the affine line, and let \(\mathcal{M}_k^{\hat \mu}\) be the localization of \(K^{\hat \mu}_0(\mathrm{Var}_k)[\mathbb{L}^{-1}]\) with respect to the multiplicative system generated by the elements \(1 - \mathbb L^i\).
Let \(f\) be a regular function on a smooth \(k\)-variety \(X\). A motivic Milnor fibre \(S_{f,x}\) of the function \(f\) at a point \(x\) in its zero locus is an element of \(\mathcal{M}_k^{\hat \mu}\) that encapsulates additive invariants of the classical Milnor fibre of \(f\) at \(x\), such as its Euler characteristic, or Hodge-Deligne polynomial, as well as the monodromy action. It was introduced by Denef and Loeser who gave a formula for \(S_{f,x}\) in terms a log-resolution of the zero locus of \(f\). Later, using the technique of motivic integration proposed by Kontsevich, Denef and Loeser gave an intrinsic definition of the motivic Milnor fibre using certain subsets of the arc space of \(X\), a variety whose \(k\)-points are in bijective correspondence with \(X(k[[t]])\). Building on their work Nicaise and Sebag introduced a rigid-analytic space called analytic Milnor fibre and computed the motivic Milnor fibre in terms of it. Their framework was more general, as it allowed to work with smooth formal \(k[[t]]\)-schemes (with the role of \(f\) played by the structure morphism).
\textit{E. Hrushovski} and \textit{D. Kazhdan} [Prog. Math. 253, 261--405 (2006; Zbl 1136.03025)] developed an alternative motivic integration theory based on model theory of algebraically closed valued fields. This theory allows one to work with rigid subanalytic sets defined by Lifshitz. Hrushovski and Loeser have shown how motivic Milnor fibre can be described in terms of an analytic Milnor fibre using this theory, also in the formal schemes setting.
The motivic Thom-Sebastiani theorem can be stated as follows. Let \(f: X \to \mathbb{A}^1\) and \(g: Y \to \mathbb{A}^1\) be regular maps, let \(S_{f,x}, S_{g,y}\) be motivic Milnor fibres of \(f\) and \(g\) at \(x \in X, y \in Y\), respectively. Denote \((f \oplus g)(x,y) = f(x) + g(y)\), and \(S^\phi_{f,x} = (-1)^{\mathrm{dim}(X)-1}(S_{f,x}-1)\) and similarly for \(S^\phi_{g,y}\). Then
\[
S^\phi_{f\oplus g, (x,y)} = S^\phi_{f,x} \ast S^\phi_{g,y}
\]
where \(\ast\) is the convolution product of varieties, extended to \(\mathcal{M}^{\hat{\mu}}\).
The reviewed article gives a new proof of the Thom-Sebastiani theorem for formal functions using the formalism of Hrushovski and Kazhdan. The proof works with analytic Milnor fibres of \(f\) and \(g\) directly, then uses the correspondence of Hrushovski and Loeser to deduce the required identity between the motivic Milnor fibres.
Reviewer: Dmitry Sustretov (Givat Ram)Efficient subformula orders for real quantifier elimination of non-prenex formulas.https://zbmath.org/1460.680862021-06-15T18:09:00+00:00"Kobayashi, Munehiro"https://zbmath.org/authors/?q=ai:kobayashi.munehiro"Iwane, Hidenao"https://zbmath.org/authors/?q=ai:iwane.hidenao"Matsuzaki, Takuya"https://zbmath.org/authors/?q=ai:matsuzaki.takuya"Anai, Hirokazu"https://zbmath.org/authors/?q=ai:anai.hirokazuSummary: In this paper we study speeding up real quantifier elimination (QE) methods for non-prenex formulas. Our basic strategy is to solve non-prenex first-order formulas by performing QE for subformulas constituting the input non-prenex formula. We propose two types of methods (heuristic methods/machine learning based methods) to determine an appropriate ordering of QE computation for the subformulas. Then we empirically examine their effectiveness through experimental results over more than 2,000 non-trivial example problems. Our experiment results suggest machine learning can save much effort spent to design effective heuristics by trials and errors without losing efficiency of QE computation.
For the entire collection see [Zbl 1334.68018].Improving a CGS-QE algorithm.https://zbmath.org/1460.130512021-06-15T18:09:00+00:00"Fukasaku, Ryoya"https://zbmath.org/authors/?q=ai:fukasaku.ryoya"Iwane, Hidenao"https://zbmath.org/authors/?q=ai:iwane.hidenao"Sato, Yosuke"https://zbmath.org/authors/?q=ai:sato.yosukeSummary: A real quantifier elimination algorithm based on computation of comprehensive Gröbner systems introduced by Weispfenning and recently improved by us has a weak point that it cannot handle a formula with many inequalities. In this paper, we further improve the algorithm so that we can handle more inequalities.
For the entire collection see [Zbl 1334.68018].Enforceable operator algebras.https://zbmath.org/1460.030092021-06-15T18:09:00+00:00"Goldbring, Isaac"https://zbmath.org/authors/?q=ai:goldbring.isaacAuthor's abstract: We adapt the classical notion of building models by games to the setting of continuous model theory. As an application, we study to what extent canonical operator algebras are enforceable models. For example, we show that the hyperfinite \(\text{II}_1\) factor is an enforceable \(\text{II}_1\) factor if and only if the Connes Embedding Problem has a positive solution. We also show that the set of continuous functions on the pseudoarc is an enforceable model of the theory of unital, projectionless, abelian \(\text{C}^{\ast}\)-algebras and use this to show that it is the prime model of its theory.
Reviewer: Daniele Mundici (Firenze)Book review of: T. Button and S. Walsh, Philosophy and model theory.https://zbmath.org/1460.000122021-06-15T18:09:00+00:00"Arana, Andrew"https://zbmath.org/authors/?q=ai:arana.andrewReview of [Zbl 1384.03001].Tame topology of arithmetic quotients and algebraicity of Hodge loci.https://zbmath.org/1460.140272021-06-15T18:09:00+00:00"Bakker, B."https://zbmath.org/authors/?q=ai:bakker.benjamin"Klingler, B."https://zbmath.org/authors/?q=ai:klingler.bruno"Tsimerman, J."https://zbmath.org/authors/?q=ai:tsimerman.jacobSummary: In this paper we prove the following results:
\begin{itemize}
\item[1)] We show that any arithmetic quotient of a homogeneous space admits a natural real semi-algebraic structure for which its Hecke correspondences are semi-algebraic. A particularly important example is given by Hodge varieties, which parametrize pure polarized integral Hodge structures.
\item[2)] We prove that the period map associated to any pure polarized variation of integral Hodge structures \(\mathbb{V}\) on a smooth complex quasi-projective variety \(S\) is definable with respect to an o-minimal structure on the relevant Hodge variety induced by the above semi-algebraic structure.
\item[3)] As a corollary of 2) and of Peterzil-Starchenko's o-minimal Chow theorem [48] we recover that the Hodge locus of \((S, \mathbb{V})\) is a countable union of algebraic subvarieties of \(S\), a result originally due to \textit{E. Cattani} et al. [ibid. 8, No. 2, 483--506 (1995; Zbl 0851.14004)]. Our approach simplifies the proof of Cattani-Deligne-Kaplan, as it does not use the full power of the difficult multivariable \(SL_2\)-orbit theorem of \textit{E. Cattani} et al. [Ann. Math. (2) 123, 457--535 (1986; Zbl 0617.14005)].
\end{itemize}Some observations on the logical foundations of inductive theorem proving.https://zbmath.org/1460.030052021-06-15T18:09:00+00:00"Hetzl, Stefan"https://zbmath.org/authors/?q=ai:hetzl.stefan"Wong, Tin Lok"https://zbmath.org/authors/?q=ai:wong.tin-lokSummary: In this paper we study the logical foundations of automated inductive theorem proving. To that aim we first develop a theoretical model that is centered around the difficulty of finding induction axioms which are sufficient for proving a goal.
Based on this model, we then analyze the following aspects: the choice of a proof shape, the choice of an induction rule and the language of the induction formula. In particular, using model-theoretic techniques, we clarify the relationship between notions of inductiveness that have been considered in the literature on automated inductive theorem proving.Model theory: groups, geometries and combinatorics. Abstracts from the workshop held January 12--18, 2020.https://zbmath.org/1460.000362021-06-15T18:09:00+00:00"Breuillard, Emmanuel (ed.)"https://zbmath.org/authors/?q=ai:breuillard.emmanuel"Martin-Pizarro, Amador (ed.)"https://zbmath.org/authors/?q=ai:martin-pizarro.amador"Tent, Katrin (ed.)"https://zbmath.org/authors/?q=ai:tent.katrin"Wagner, Frank Olaf (ed.)"https://zbmath.org/authors/?q=ai:wagner.frank-oSummary: The focus of the conference were recent interactions between model theory, group theory and combinatorics in finite geometries. In some cases, in particular in non-archimedean geometry or combinatorics in finite geometries, model theory appeared as tool. In other cases, like in ergodic theory and dynamics or in the theory of stable groups and more general neo-stable algebraic structures like valued fields, the focus was on model theoretic questions and classification results for such structures. In this way, the conference presented the broad range of topics of modern model theory.First-order interpolation derived from propositional interpolation.https://zbmath.org/1460.030062021-06-15T18:09:00+00:00"Baaz, Matthias"https://zbmath.org/authors/?q=ai:baaz.matthias"Lolic, Anela"https://zbmath.org/authors/?q=ai:lolic.anelaWhile interpolation properties in a propositional logic $L$ usually hinge upon the underlying algebras of $L$, the study of interpolation in first-order logics does not have a similar algebraic flavor. In the paper under review the authors give a method to reduce first-order to propositional interpolation. Suitable skolemizations and Herbrand expansions are constructed which, combined with a \textit{propositional} interpolant, yield a \textit{first-order} interpolant. The proof-theoretic constructions of this paper are applicable to lattice-based finite-valued logics and to the weak quantifier and subprenex fragments of infinitely-valued first-order Gödel logic. Interpolation turns out to be decidable for these logics.
Reviewer: Daniele Mundici (Firenze)The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws.https://zbmath.org/1460.680422021-06-15T18:09:00+00:00"Cozman, Fabio Gagliardi"https://zbmath.org/authors/?q=ai:gagliardi-cozman.fabio"Mauá, Denis Deratani"https://zbmath.org/authors/?q=ai:maua.denis-derataniSummary: This paper studies specification languages that describe Bayesian networks using predicates and other logical constructs. First, we adopt an abstract syntax for relational Bayesian network specifications, and review definability and complexity results. We then propose a novel framework to study the descriptive complexity of relational Bayesian network specifications, and show that specifications based on function-free first-order logic capture the complexity class \(\mathsf{PP} \); we also exhibit specification languages, based on second-order quantification, that capture the hierarchy of complexity classes \(\mathsf{PP}^{\mathsf{NP}^{\ldots \mathsf{NP}}} \), a result that does not seem to have equivalent in the literature. Finally, we derive zero/one laws for Bayesian network specifications based on function-free first-order logic, indicating their value in definability analysis.Model-checking for successor-invariant first-order formulas on graph classes of bounded expansion.https://zbmath.org/1460.680662021-06-15T18:09:00+00:00"van den Heuvel, Jan"https://zbmath.org/authors/?q=ai:van-den-heuvel.jan"Kreutzer, Stephan"https://zbmath.org/authors/?q=ai:kreutzer.stephan"Pilipczuk, Michał"https://zbmath.org/authors/?q=ai:pilipczuk.michal"Quiroz, Daniel A."https://zbmath.org/authors/?q=ai:quiroz.daniel-a"Rabinovich, Roman"https://zbmath.org/authors/?q=ai:rabinovich.roman"Siebertz, Sebastian"https://zbmath.org/authors/?q=ai:siebertz.sebastianA closedness theorem over Henselian fields with analytic structure and its applications.https://zbmath.org/1460.320472021-06-15T18:09:00+00:00"Nowak, Krzysztof Jan"https://zbmath.org/authors/?q=ai:nowak.krzysztof-janSummary: In this brief note, we present our closedness theorem in geometry over Henselian valued fields with analytic structure. It enables, among others, application of resolution of singularities and of transformation to normal crossings by blowing up in much the same way as over locally compact ground fields. Also given are many applications which, at the same time, provide useful tools in geometry and topology of definable sets and functions. They include several versions of the Łojasiewicz inequality, Hölder continuity of definable functions continuous on closed bounded subsets of the affine space, piecewise continuity of definable functions or curve selection. We also present our most recent research concerning definable retractions and the extension of continuous definable functions. These results were established in several successive papers of ours, and their proofs made, in particular, use of the following fundamental tools: elimination of valued field quantifiers, term structure of definable functions and b-minimal cell decomposition, due to Cluckers-Lipshitz-Robinson, relative quantifier elimination for ordered abelian groups, due to Cluckers-Halupczok, the closedness theorem as well as canonical resolution of singularities and transformation to normal crossings by blowing up due to Bierstone-Milman. As for the last tool, our approach requires its definable version established in our most recent paper within a category of definable, strong analytic manifolds and maps.
For the entire collection see [Zbl 1460.13001].On the axiomatisability of the dual of compact ordered spaces.https://zbmath.org/1460.180112021-06-15T18:09:00+00:00"Abbadini, Marco"https://zbmath.org/authors/?q=ai:abbadini.marco"Reggio, Luca"https://zbmath.org/authors/?q=ai:reggio.lucaSummary: We provide a direct and elementary proof of the fact that the category of Nachbin's compact ordered spaces is dually equivalent to an \(\aleph_1\)-ary variety of algebras. Further, we show that \(\aleph_1\) is a sharp bound: compact ordered spaces are not dually equivalent to any SP-class of finitary algebras.Thirty years of virtual substitution. Foundations, techniques, applications.https://zbmath.org/1460.030072021-06-15T18:09:00+00:00"Sturm, Thomas"https://zbmath.org/authors/?q=ai:sturm.thomas-p|sturm.thomas-fSynthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT.https://zbmath.org/1460.680992021-06-15T18:09:00+00:00"Rocha, Thiago Alves"https://zbmath.org/authors/?q=ai:alves-rocha.thiago"Martins, Ana Teresa"https://zbmath.org/authors/?q=ai:martins.ana-teresa"Ferreira, Francicleber Martins"https://zbmath.org/authors/?q=ai:martins-ferreira.francicleberSummary: We present a method to extract knowledge in terms of quantifier-free sentences in disjunctive normal form from noisy samples of classified strings. We show that the problem to find such a sentence is NP-complete, and our approach for solving it is based on a reduction to the Boolean satisfiability problem. Moreover, our method bounds the number of disjuncts and the maximum number of literals per clause since sentences with few clauses and few literals per clause are easier to interpret. As the logic we are considering defines exactly the class of locally threshold testable (LTT) languages, our results can be useful in grammatical inference when the goal is to find a model of an LTT language from a sample of strings. We also use results of the Ehrenfeucht-Fraïssé game over strings in order to handle consistent and inconsistent samples of strings.