Homing vector automata

DOI10.1051/ITA/2016017MaRDI QIDQ2969985zbMATH OpenOpenAlexFDO

Authors Özlem Salehi, A. C. Cem Say, Flavio D'Alessandro

Publication date 24 March 2017

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.09185, http://hdl.handle.net/11573/923087

zbMATH Keywords

group automatavector automataStern-Brocot encoding

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Abstract: 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.

Recommendations

• Real-time vector automata
• New results on vector and homing vector automata
• On the Length of Homing Sequences for Nondeterministic Finite State Machines
• scientific article; zbMATH DE number 1223712
• A note on homogeneous experiments with finite automata

Cites work

• scientific article; zbMATH DE number 3875506 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• A multidimensional continued fraction generalization of Stern's diatomic sequence
• Counter machines and counter languages
• EXTENDED FINITE AUTOMATA AND WORD PROBLEMS
• Extended finite automata over groups
• Finite automata over free groups
• Finite automata with multiplication
• Formal Languages and Groups as Memory
• Generalized Automata and Stochastic Languages
• Quantum algorithms via linear algebra. A primer
• Real-time vector automata
• Remarks on blind and partially blind one-way multicounter machines
• Simulations by time-bounded counter machines

Cited in

(2)

• New results on vector and homing vector automata
• Real-time vector automata

This page was built for publication: Homing vector automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969985)