no. 4
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, Tome 50 (2016) no. 4, pp. 371-386.

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
Mots clés : 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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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, Tome 50 (2016) no. 4, pp. 371-386. doi : 10.1051/ita/2016017. http://www.numdam.org/articles/10.1051/ita/2016017/

A. Brocot, Calcul des rouages par approximation, nouvelle méthode. Revue Chronométrique 3 (1861) 186–194.

N. Chomsky, Context-free grammars and pushdown storage. M. I. T. Res. Lab. Electron. Quart. Prog. Report. 65 (1962) 187–194.

J.M. Corson, Extended finite automata and word problems. Int. J. Algebra Comput. 15 (2005) 455–466. | DOI | MR | Zbl

J. Dassow and V. Mitrana, Finite automata over free groups. Int. J. Algebra Comput. 10 (2000) 725–737. | DOI | MR | Zbl

P.C. Fischer, A.R. Meyer and A.L. Rosenberg, Real time counter machines. In Proc. of the 8th Annual Symposium on Switching and Automata Theory (SWAT 1967), FOCS ’67 (1967) 148–154.

P.C. Fischer, A.R. Meyer and A.L. Rosenberg, Counter machines and counter languages. Math. Syst. Theory 2 (1968) 265–283. | DOI | MR | Zbl

Th. Garrity, A multidimensional continued fraction generalization of sterns diatomic sequence. J. Integer Seq. 16 (2013) 3. | MR

R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science. Addison Wesley (1989). | MR | Zbl

S.A. Greibach, Remarks on blind and partially blind one-way multicounter machines. Theor. Comput. Sci. 7 (1978) 311–324. | DOI | MR | Zbl

O.H. Ibarra, S.K. Sahni and Ch.E. Kim, Finite automata with multiplication. Theor. Comput. Sci. 2 (1976) 271–294. | DOI | MR | Zbl

M. Kambites, Formal languages and groups as memory. Commun. Algebra 37 (2009) 193–208. | DOI | MR | Zbl

M.I. Kargapolov and J.I. Merzljakov, Fundamentals of the Theory of Groups. Springer Verlag (1979). | MR | Zbl

R.J. Lipton and K.W. Regan, Quantum Algorithms via Linear Algebra. MIT Press (2014). | MR

R.C. Lyndon and P.E. Schupp, Combinatorial Group Theory. Springer Verlag (1977). | MR | Zbl

V. Mitrana and R. Stiebe, The accepting power of finite automata over groups. In New Trends in Formal Languages. Springer Verlag (1997) 39–48. | MR

V. Mitrana and R. Stiebe, Extended finite automata over groups. Discrete Appl. Math. 108 (2001) 287–300. | DOI | MR | Zbl

H. Petersen, Simulations by time-bounded counter machines. Int. J. Found. Comput. Sci. 22 (2011) 395–409. | DOI | MR | Zbl

Ö. Salehi, A. Yakaryılmaz and A.C.C. Say, Real-time vector automata. In Proc. of the 19th International Conference on Fundamentals of Computation Theory, FCT’13. Springer Verlag (2013) 293–304. | MR

M.A. Stern, Über eine zahlentheoretische Funktion. J. Reine Angew. Math. 55 (1858) 193–220. | MR

P. Turakainen, Generalized automata and stochastic languages. Proc. of the American Mathematical Society 21 (1969) 303–309. | DOI | MR | Zbl

Cité par Sources :