Reference : On Iterating Linear Transformations over Recognizable Sets of Integers |

Scientific journals : Article | |||

Engineering, computing & technology : Computer science | |||

http://hdl.handle.net/2268/74862 | |||

On Iterating Linear Transformations over Recognizable Sets of Integers | |

English | |

Boigelot, Bernard [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique >] | |

2003 | |

Theoretical Computer Science | |

Elsevier Science | |

309 | |

1-3 | |

413-468 | |

Yes (verified by ORBi) | |

International | |

0304-3975 | |

Amsterdam | |

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). | |

Researchers | |

http://hdl.handle.net/2268/74862 | |

10.1016/S0304-3975(03)00314-1 | |

This is the author's version of the work. The published version is available online at http://dx.doi.org/10.1016/S0304-3975(03)00314-1 |

File(s) associated to this reference | ||||||||||||||

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

All documents in ORBi are protected by a user license.