Geodesic
Homing vector automata
Salehi, Özlem1  ; Cem Say, A. C.1 ; D’Alessandro, Flavio2, 3
1 Boǧaziçi University, Department of Computer Engineering, Bebek 34342, Istanbul, Turkey.
2 Boğaziçi University, Department of Mathematics, Bebek 34342, Istanbul, Turkey.
3 Università di Roma “La Sapienza”, Dipartimento di Matematica, Piazzale Aldo Moro 2, 00185 Roma, Italy.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 7th Non-Classical Models of Automata and Applications (NCMA-2015) , Tome 50 (2016) no. 4, pp. 371-386

Voir la notice de l'article provenant de la source Numdam

We introduce homing vector automata, which are finite automata augmented by a vector that is multiplied at each step by a matrix determined by the current transition, and have to return the vector to its original setting in order to accept the input. The computational power and properties of deterministic, nondeterministic, blind, non-blind, real-time and one-way versions of these machines are examined and compared to various related types of automata. A generalized version of the Stern−Brocot encoding method, suitable for representing strings on arbitrary alphabets, is also developed.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016017
Classification : 68Q45, 68Q05
Keywords: Vector automata, group automata, Stern−Brocot

Salehi, Özlem 1 ; Cem Say, A. C. 1 ; D’Alessandro, Flavio 2, 3

1 Boǧaziçi University, Department of Computer Engineering, Bebek 34342, Istanbul, Turkey.
2 Boğaziçi University, Department of Mathematics, Bebek 34342, Istanbul, Turkey.
3 Università di Roma “La Sapienza”, Dipartimento di Matematica, Piazzale Aldo Moro 2, 00185 Roma, Italy. 
@article{ITA_2016__50_4_371_0,
     author = {Salehi, \"Ozlem and Cem Say, A. C. and D{\textquoteright}Alessandro, Flavio},
     title = {Homing vector automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {371--386},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {4},
     year = {2016},
     doi = {10.1051/ita/2016017},
     mrnumber = {3614551},
     zbl = {1362.68154},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2016017/}
}
TY  - JOUR
AU  - Salehi, Özlem
AU  - Cem Say, A. C.
AU  - D’Alessandro, Flavio
TI  - Homing vector automata
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 371
EP  - 386
VL  - 50
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2016017/
DO  - 10.1051/ita/2016017
LA  - en
ID  - ITA_2016__50_4_371_0
ER  - 
%0 Journal Article
%A Salehi, Özlem
%A Cem Say, A. C.
%A D’Alessandro, Flavio
%T Homing vector automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 371-386
%V 50
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2016017/
%R 10.1051/ita/2016017
%G en
%F ITA_2016__50_4_371_0
Salehi, Özlem; Cem Say, A. C.; D’Alessandro, Flavio. Homing vector automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 7th Non-Classical Models of Automata and Applications (NCMA-2015) , Tome 50 (2016) no. 4, pp. 371-386. doi: 10.1051/ita/2016017

Cité par Sources :