Search

For some Maltsev conditions Σ it is enough to check if a finite algebra A satisfies Σ locally on subsets of bounded size in order to decide whether A satisfies Σ (globally). This local–global property is the main known source of tractability results for deciding Maltsev conditions. In this paper, we investigate the local–global property for the existence of a G-term, i.e. an n -ary term that is invariant under permuting its variables according to a permutation group G ≤ Sym (n). Our results imply in particular that all cyclic loop conditions (in the sense of Bodirsky, Starke, and Vucaj) have the local–global property (and thus can be decided in polynomial time), while symmetric terms of arity n > 2 fail to have it. [ABSTRACT FROM AUTHOR]

For relational structures A, B of the same signature, the Promise Constraint Satisfaction Problem PCSP(A, B) asks whether a given input structure maps homomorphically to A or does not even map to B. We are promised that the input satisfies exactly one of these two cases. If there exists a structure C with homomorphisms A → C → B, then PCSP(A, B) reduces naturally to CSP(C). To the best of our knowledge all known tractable PCSPs reduce to tractable CSPs in this way. However Barto [Bar19] showed that some PCSPs over finite structures A, B require solving CSPs over infinite C. We show that even when such a reduction to some finite C is possible, this structure may become arbitrarily large. For every integer n > 1 and every prime p we give A, B of size n with a single relation of arity n p such that PCSP(A, B) reduces via a chain of homomorphisms A → C → B to a tractable CSP over some C of size p but not over any smaller structure. In a second family of examples, for every prime p ≥ 7 we construct A, B of size p − 1 with a single ternary relation such that PCSP(A, B) reduces via A → C → B to a tractable CSP over some C of size p but not over any smaller structure. In contrast we show that if A, B are graphs and PCSP(A, B) reduces to a tractable CSP(C) for some finite digraph C, then already A or B has a tractable CSP. This extends results and answers a question of [DSM+21]. [ABSTRACT FROM AUTHOR]

We show that for a fixed positive integer k one can efficiently decide if a finite algebra A admits a k-ary weak near unanimity operation by looking at the local behavior of the terms of A. We also observe that the problem of deciding if a given finite algebra has a quasi Taylor operation is solvable in polynomial time by looking, essentially, for local quasi Siggers operations. [ABSTRACT FROM AUTHOR]

We characterize absorption in finite idempotent algebras by means of Jónsson absorption and cube term blockers. As an application we show that it is decidable whether a given subset is an absorbing subuniverse of an algebra given by the tables of its basic operations. [ABSTRACT FROM AUTHOR]

We study the complexity of computation in finitely generated free left, right and two-sided adequate semigroups and monoids. We present polynomial time (quadratic in the RAM model of computation) algorithms to solve the word problem and compute normal forms in each of these, and hence to test whether any given identity holds in the classes of left, right and/or two-sided adequate semigroups. [ABSTRACT FROM AUTHOR]

The Mööbius number systems use sequences of Mööbius transformations to represent the extended real line or, equivalently, the unit complex circle. An infinite sequence of Mööbius transformations represents a point x on the circle if and only if the transformations, in the limit, take the uniform measure on the circle to the Dirac measure centered at the point x. We present new characterizations of this convergence. Moreover, we show how to improve a known result that guarantees the existence of Mööbius number systems for some Mööbius iterative systems. As Mööbius number systems use subshifts instead of the whole symbolic space, we can ask what is the language complexity of these subshifts. We offer (under some assumptions) a sufficient and necessary condition for a number system to be sofic. [ABSTRACT FROM AUTHOR]

The paper gives a characterisation of the chain relation of a sofic subshift. Every sofic subshift Σ can be described by a labelled graph G. Factorising G in a suitable way we obtain the graph G/≈ that offers insight into some properties of the original subshift. Using G/≈ we describe first the chain relation in Σ, then characterise chain-transitive sofic subshifts, chain-mixing sofic subshifts and finally the attractors of the subshift dynamic system. At the end we present (straightforward) algorithms deciding chain-transitivity and chain-mixing properties of a sofic subshift and listing all the attractors of the subshift system. [ABSTRACT FROM AUTHOR]