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 [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique >] | |

Rassart, Stéphane [> >] | |

Wolper, Pierre [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 | ||||||||||||||

| ||||||||||||||

All documents in ORBi are protected by a user license.