Reference : On Iterating Linear Transformations over Recognizable Sets of Integers
Scientific journals : Article
Engineering, computing & technology : Computer science
On Iterating Linear Transformations over Recognizable Sets of Integers
Boigelot, Bernard mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique >]
Theoretical Computer Science
Elsevier Science
Yes (verified by ORBi)
The Netherlands
[en] automata ; Presburger arithmetic ; iterations
[en] It has been known for a long time that the sets of integer vectors
that are recognizable by finite-state automata are those that can be
defined in an extension of Presburger arithmetic. In this paper, we
address the problem of deciding whether the closure of a linear
transformation preserves the recognizable nature of sets of integer
vectors. We solve this problem by introducing an original extension of
the concept of recognizability to sets of vectors with complex
components. This generalization allows to obtain a simple necessary
and sufficient condition over linear transformations, in terms of the
eigenvalues of the transformation matrix. We then show that these
eigenvalues do not need to be computed explicitly in order to evaluate
the condition, and we give a full decision procedure based on simple
integer arithmetic. The proof of this result is constructive, and can
be turned into an algorithm for applying the closure of a linear
transformation that satisfies the condition to a finite-state
representation of a set. Finally, we show that the necessary and
sufficient condition that we have obtained can straightforwardly be
turned into a sufficient condition for linear transformations with
linear guards.
This work was partially funded by a grant of the "Communauté française de Belgique - Direction de la recherche scientifique - Actions de recherche concertées", and by the European Commission (FET project ADVANCE, contract No IST-1999-29082).
This is the author's version of the work. The published version is available online at

File(s) associated to this reference

Fulltext file(s):

Open access
b03-preprint.pdfAuthor preprint436.42 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.