🔬 Research > Preprints
Regularity as seen by Alice and Bob.
Abstract
The goal of this paper is to propose a machine-independent characterisation of functions computable by finite-state automata. Inspired by communication complexity, we introduce a model of computation that defines functions of type Σ^(*) → 𝔻, where Σ is a finite alphabet and 𝔻 is some domain. Domains of interest include: the Booleans, strings, or a field. In the model, the input string w is split into two parts w = w₁w₂, which are sent to two parties, Alice and Bob. The two parties cooperate, exchanging a constant number of messages to compute the output of the function. The messages can be either bits, or elements of the output domain. They must produce the correct output regardless of the split w = w₁w₂. For some domains, the model coincides with known finite state models: in the case of Boolean outputs it defines exactly the regular languages, and in the case of fields, it defines exactly the functions computable by weighted automata. We also conjecture that a similar situation arises for other domains, and present ample supporting evidence.Computability of Equivariant Gröbner bases.
Abstract
Let 𝕂 be a field, 𝒳 be an infinite set (of indeterminates), and 𝒢 be a group acting on 𝒳. An ideal in the polynomial ring 𝕂[𝒳] is called equivariant if it is invariant under the action of 𝒢. We show Gröbner bases for equivariant ideals are computable are hence the equivariant ideal membership is decidable when 𝒢 and 𝒳 satisfies the Hilbert’s basis property, that is, when every equivariant ideal in 𝕂[𝒳] is finitely generated. Moreover, we give a sufficient condition for the undecidability of the equivariant ideal membership problem. This condition is satisfied by the most common examples not satisfying the Hilbert’s basis property. Our results imply decidability of solvability of orbit-finite systems of linear equations and the reachability problem for reversible data Petri nets for a large class of data domains.N-polyregular functions arise from well-quasi-orderings.
Abstract
A fundamental construction in formal language theory is the Myhill-Nerode congruence on words, whose finiteness characterizes regular language. This construction was generalized to functions from finite words to ℤ by Colcombet, Douéneau-Tabot, and Lopez to characterize the class of so-called ℤ-polyregular functions. In this paper, we relax the notion of equivalence relation to quasi-ordering in order to study the class of ℕ-polyregular functions, that plays the role of ℤ-polyregular functions among functions from finite words to ℕ. The analogue of having a finite index is then being a well-quasi-ordering. This provides a canonical object to describe ℕ-polyregular functions, together with a powerful new characterization of this class.Measuring well-quasi-ordered finitary powersets.
Abstract
The complexity of a well-quasi-order (wqo) can be measured through three classical ordinal invariants: the width as a measure of antichains, the height as a measure of chains, and the maximal order type as a measure of bad sequences. This article considers the "finitary powerset" construction: the collection Pf(X) of finite subsets of a wqo X ordered with the Hoare embedding relation remains a wqo. The width, height and maximal order type of Pf(X) cannot be expressed as a function of the invariants of X, and we provide tight upper and lower bounds for the three invariants. The article also identifies an algebra of well-behaved wqos, that include finitary powersets as well as other more classical constructions, and for which the ordinal invariants can be computed compositionnally. This relies on a new ordinal invariant called the approximated maximal order type.