Narrow Results

Language equations with all Boolean operations and concatenation and a particular order on the set of solutions are proved to be equal in expressive power to the first-order Peano arithmetic. In particular, it is shown that the class of sets representable using k variables (for every k ≥ 2) is exactly the k-th level of the arithmetical hierarchy, i.e., the sets definable by recursive predicates with k alternating quantifiers. The property of having an extremal solution is shown to be nonrepresentable in first-order arithmetic.

A famous theorem of Kuratowski states that, in a topological space, at most 14 distinct sets can be produced by repeatedly applying the operations of closure and complement to a given set. We re-examine this theorem in the setting of formal languages, where by "closure" we mean either Kleene closure or positive closure. We classify languages according to the structure of the algebras they generate under iterations of complement and closure. There are precisely 9 such algebras in the case of positive closure, and 12 in the case of Kleene closure. We study how the properties of being open and closed are preserved under concatenation. We investigate analogues, in formal languages, of the separation axioms in topological spaces; one of our main results is that there is a clopen partition separating two words if and only if the words do not commute. We can decide in quadratic time if the language specified by a DFA is closed, but if the language is specified by an NFA, the problem is PSPACE-complete.

Let $\sum$ be a finite alphabet and ${\sum }^{*}$ the set of all words over $\sum$. A subword-free language (also known as a hypercode) is an independent subset of ${\sum }^{*}$ with respect to the embedding order (denoted by ${\le }_{\mathscr{H}}$) on ${\sum }^{*}$. In this paper we introduce three subsets of the partial order ${\le }_{\mathscr{H}}$, and study three subclasses of languages defined by these subsets. They are out subword-free languages, left subword-free languages and right subword-free languages. The properties of these languages are established for determining their combinatorial and algebraic structures. By equipping them with two binary operations, respectively, all these classes of languages form semilattice-ordered semigroups. It is shown that they are freely generated by $\sum$ in three subvarieties of semilattice-ordered semigroups, respectively. It is also shown that the word problems for these free algebras are solvable.

We define a new strict and computable hierarchy for the family of automaton semigroups, which reflects the various asymptotic behaviors of the state-activity growth. This hierarchy extends that given by Sidki for automaton groups, and also gives new insights into the latter. Its exponential part coincides with a notion of entropy for some associated automata.

We prove that the Order Problem is decidable whenever the state-activity is bounded. The Order Problem remains open for the next level of this hierarchy, that is, when the state-activity is linear. Gillibert showed that it is undecidable in the whole family.

We extend the aforementioned hierarchy via a semi-norm making it more coarse but somehow more robust and we prove that the Order Problem is still decidable for the first two levels of this alternative hierarchy.

For some distinguished properties of semigroups, such as having idempotents, regularity, hopficity, etc., we study the following: whether that property or its negation is a Markov property, whether it is decidable for finitely presented semigroups and for one-relation semigroups and monoids. All the results and open problems are summarized in a table.

We address the following decision problem. Given a numeration system U and a U-recognizable set $X\subseteq \mathbb{N}$, i.e. the set of its greedy U-representations is recognized by a finite automaton, decide whether or not X is ultimately periodic. We prove that this problem is decidable for a large class of numeration systems built on linear recurrence sequences. Based on arithmetical considerations about the recurrence equation and on p-adic methods, the DFA given as input provides a bound on the admissible periods to test.

Let us consider a classical problem of decision-making with fuzzy rewards. In order to choose the alternative which corresponds to the best fuzzy reward, we need to use a total order for the fuzzy numbers involved in the problem. In this paper, we consider a definition of such a total order, which is based upon two subjective aspects: the degree of optimism/pessimism and the liking for risk/safety. We also use the graded numbers which are analogous to the fuzzy numbers. However, the operations with graded numbers are carried out as a simple extension of operations with real intervals.

We consider a natural generalization of the concept of order of an element in a group $G$: an element $g\in G$ is said to have order $k$ in a subgroup $H$ (respectively, in a coset $Hu$) of $G$ if $k$ is the first strictly positive integer such that $g^k\in H$ (respectively, $g^k\in Hu$). We study this notion and its algorithmic properties in the realm of free groups and some related families.

Both positive and negative (algorithmic) results emerge in this setting. On the positive side, among other results, we prove that the order of elements, the set of orders (called spectrum), and the set of preorders (i.e. the set of elements of a given order) with respect to finitely generated subgroups are always computable in free and free times free-abelian groups. On the negative side, we provide examples of groups and subgroups having essentially any subset of natural numbers as relative spectrum; in particular, non-recursive and even not computably enumerable sets of natural numbers. Also, we take advantage of Mikhailova’s construction to see that the spectrum membership problem is unsolvable for direct products of nonabelian free groups.

Undecidability reflects a fundamental limit to logical reasoning that permeates formal analysis in diverse areas of natural and social sciences. We present an intuitive approach to understanding how undecidability may emerge endogenously in modeling a wide range of real-world problems. Not only does this allow for a better understanding of these problems, but it also provides a gateway for a holistic approach to rational decision-making.

When the variance is known, a level 1 – α confidence interval of specified width 2h > 0 for the mean of a normal distribution requires a sample of size at least η = c²σ²/h², where c is the upper quantile of the standard normal distribution. If the variance is unknown, then such an interval may be constructed using Stein's double sampling procedure in which an initial sample of size m ≥ 2 is drawn and used to estimate η. Here is it shown that if the experimenter can specify a prior guess, η₀ say, for η, then is an approximately minimax choice for the initial sample size. The formulation is, in fact, more general and includes point estimation with equivariant loss as well as interval estimation.