Narrow Results

We discuss the role of scale dependence of entropy/complexity and its relationship to component interdependence. The complexity as a function of scale of observation is expressed in terms of subsystem entropies for a system having a description in terms of variables that have the same a priori scale. The sum of the complexity over all scales is the same for any system with the same number of underlying degrees of freedom (variables), even though the complexity at specific scales differs due to the organization/interdependence of these degrees of freedom. This reflects a tradeoff of complexity at different scales of observation. Calculation of this complexity for a simple frustrated system reveals that it is possible for the complexity to be negative. This is consistent with the possibility that observations of a system that include some errors may actually cause, on average, negative knowledge, i.e. incorrect expectations.

A limit variety is a variety that is minimal with respect to being nonfinitely based. This paper presents a new infinite series of limit semigroup varieties, each of which is generated by a finite 0-simple semigroup with Abelian subgroups. These varieties exhaust all limit varieties generated by completely 0-simple semigroups with Abelian subgroups.

Let 𝔽_q stand for the finite field of odd characteristic p with q elements (q = pⁿ, n ∈ ℕ) and ${\mathbb{F}}_q^{*}$ denote the set of all the nonzero elements of 𝔽_q. Let m and t be positive integers. By using the Smith normal form of the exponent matrix, we obtain a formula for the number of rational points on the variety defined by the following system of equations over ${\mathbb{F}}_q:{\displaystyle \sum _{j=0}^{t-1}{\displaystyle \sum _{i=1}^{r_{j+1}-r_j}{a}_{k,r_j+i}{x}_1{}^{e_{r_j+i,1}^{\left(k\right)}}\dots x_{n_{j+1}}^{e_{r_j+i,n_{j+1}}^{\left(k\right)}}=b_{k,}}}k=1,\dots ,m,$ where the integers t > 0, r₀ = 0 < r₁ < r₂ < ⋯ < r_t, 1 ≤ n₁ < n₂ <, ⋯ < n_t and 0 ≤ j ≤ t − 1, b_k ∊ 𝔽_q, a_k,i ∊ ${\mathbb{F}}_q^{*}$ (k = 1, …, m, i = 1, …, r_t), and the exponent of each variable is a positive integer. Further, under some natural conditions, we arrive at an explicit formula for the number of 𝔽_q-rational points on the above variety. It extends the results obtained previously by Wolfmann, Sun, Wang, Hong et al. Our result gives a partial answer to an open problem raised in [The number of rational points of a family of hypersurfaces over finite fields, J. Number Theory156 (2015) 135–153].

We say that a finite algebra 𝔸 = 〈A; F〉 has the ability to count if there are subalgebras C of 𝔸³ and Z of 𝔸 such that the structure 〈A; C, Z〉 has the ability to count in the sense of Feder and Vardi. We show that for a core relational structure A the following conditions are equivalent: (i) the variety generated by the algebra 𝔸 associated to A contains an algebra with the ability to count; (ii) 𝔸² has the ability to count; (iii) the variety generated by 𝔸 admits the unary or affine type. As a consequence, for CSP's of finite signature, the bounded width conjectures stated in Feder–Vardi [10], Larose–Zádori [17] and Bulatov [5] are identical.

A variety of algebras is called limit if it is nonfinitely-based but all its proper subvarieties are finitely-based. A monoid is aperiodic if all its subgroups are trivial. We classify all limit varieties of aperiodic monoids with commuting idempotents.

Let F_q be the finite field with q elements and n ≥ 2 an integer. We provide a bound on the number of 𝔽_q-rational points of the hypersurfaces in the affine space and in the projective space of dimension n, defined on 𝔽_q which are irreducible over 𝔽_q but non-absolutely irreducible.

A semiring with involution is a semiring equipped with an involutorial antiasutomorphism as a fundamental operation. The aim of the present paper is to determine the lattice of all varieties of idempotent and distributive semirings with involution. We start with the description of their structure, which is followed by a complete list of all subdirectly irreducibles. We make a heavy use of general results obtained recently by Dolinka and Vinčić [11] on involutorial Płonka sums. Applying these results and some further structural theorems, we construct the considered lattice. It turns out that it has exactly 64 elements.

Let W(X) be a free commutative or a free associative algebra. The group of automorphisms of the semigroup End(W(X)) is studied.

An $n$-ary operation $f$ is called symmetric if, for all permutations $\pi$ of $\{1,\dots ,n\}$, it satisfies the identity $f(x_1,x_2,\dots ,x_n)=f(x_{\pi (1)},x_{\pi (2)},\dots ,x_{\pi (n)})$. We show that, for each finite algebra ${𝒜}$, either it has symmetric term operations of all arities or else some finite algebra in the variety generated by ${𝒜}$ has two automorphisms without a common fixed point. We also show this two-automorphism condition cannot be replaced by a single fixed-point-free automorphism.

This paper is motivated by the work of Schützenberger on codes with bounded synchronization delay. He was interested in characterizing those regular languages where groups in the syntactic monoid belong to a variety $H$. On the language side he allowed the operations union, intersection, concatenation and modified Kleene-star involving a mapping of a prefix code of bounded synchronization delay to a group $G\in H$, but no complementation. In our notation, this leads to the language classes ${SD}_H(A^{\infty })$. Our main result shows that ${SD}_H(A^{\infty })$ coincides with the class of languages having syntactic monoids where all subgroups are in $H$. We show that this statement holds for all varieties $H$ of finite groups, whereas Schützenberger proved this result for varieties $H$ containing Abelian groups, only. Our method shows the result for all $H$ simultaneously on finite and infinite words. Furthermore, we introduce the notion of local Rees extension which refers to a restricted type of the classical Rees extension. We give a decomposition of a monoid in terms of its groups and local Rees extensions. This gives a somewhat similar, but simpler decomposition than in the synthesis theorem of Rhodes and Allen. Moreover, we need a singly exponential number of operations, only. Finally, our decomposition yields an answer to a question in a recent paper of Almeida and Klíma about varieties that are closed under Rees extensions.

In this paper, we first show that the variety ${𝒱}$ of posemigroups satisfying an identity $axy=axay$ is closed if it is ${𝒱}$-convex. Next, we show that inverse posemigroups satisfying an identity $x=xyx$ are absolutely closed. We also show that a convex variety of left [right] zero posemigroups is absolutely closed and finally $U^0$ is absolutely closed if so is $U$.