Real-time vector automata

DOI10.1007/978-3-642-40164-0_28MaRDI QIDQ2842793zbMATH OpenOpenAlexFDO

Authors Özlem Salehi, Abuzer Yakaryılmaz, A. C. Cem Say

Publication date 16 August 2013

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.6129

zbMATH Keywords

counter automatageneralized automataautomata with multiplicationvector automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We study the computational power of real-time finite automata that have been augmented with a vector of dimension k, and programmed to multiply this vector at each step by an appropriately selected $kimesk$ matrix. Only one entry of the vector can be tested for equality to 1 at any time. Classes of languages recognized by deterministic, nondeterministic, and "blind" versions of these machines are studied and compared with each other, and the associated classes for multicounter automata, automata with multiplication, and generalized finite automata.

Recommendations

• Homing vector automata
• New results on vector and homing vector automata
• scientific article; zbMATH DE number 1223712
• A note on realtime one-way synchronized alternating one-counter automata
• Vectorial languages and linear temporal logic

Cited in

(5)

• New results on vector and homing vector automata
• A survey of state vectors
• Homing vector automata
• Vectorial languages and linear temporal logic
• Group Input Machine

This page was built for publication: Real-time vector automata

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