Reference : On the Expressiveness of Real and Integer Arithmetic Automata
Scientific congresses and symposiums : Paper published in a journal
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/74876
On the Expressiveness of Real and Integer Arithmetic Automata
English
Boigelot, Bernard mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique >]
Rassart, Stéphane [> >]
Wolper, Pierre mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique > >]
1998
Lecture Notes in Computer Science
Springer
1443
152-163
Yes
No
International
0302-9743
1611-3349
Berlin
Germany
Automata, Languages and Programming, 25th International Colloquium (ICALP'98)
13-17 July, 1998
Aalborg
Denmark
[en] automata ; real-vector automata ; mixed integer and real arithmetic
[en] If read digit by digit, a n-dimensional vector of integers
represented in base r can be viewed as a word over the alphabet
r to the n. It has been known for some time that, under this encoding, the
sets of integer vectors recognizable by finite automata are exactly
those definable in Presburger arithmetic if independence with respect
to the base is required, and those definable in a slight extension of
Presburger arithmetic if only a specific base is considered.

Using the same encoding idea, but moving to infinite words, finite
automata on infinite words can recognize sets of real vectors. This
leads to the question of which sets of real vectors are recognizable
by finite automata, which is the topic of this paper. We show that
the recognizable sets of real vectors are those definable in the
theory of reals and integers with addition and order, extended with a
special base-dependent predicate that tests the value of a specified
digit of a number. Furthermore, in the course of proving that sets
of vectors defined in this theory are recognizable by finite
automata, we show that linear equations and inequations have
surprisingly compact representations by automata, which leads us to
believe that automata accepting sets of real vectors can be of more
than theoretical interest.
Fonds de la Recherche Scientifique (Communauté française de Belgique) - F.R.S.-FNRS
Researchers
http://hdl.handle.net/2268/74876
http://link.springer.de/link/service/series/0558/bibs/1443/14430152.htm
The original publication is available at www.springerlink.com

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
BRW08.pdfAuthor preprint325.38 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.