New results on vector and homing vector automata

DOI10.1142/S0129054119500291MaRDI QIDQ5207237zbMATH OpenOpenAlexFDO

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

Publication date 19 December 2019

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

finite automatagroup automatahoming vector automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Linear Diophantine equations (11D04)

Abstract: We present several new results and connections between various extensions of finite automata through the study of vector automata and homing vector automata. We show that homing vector automata outperform extended finite automata when both are defined over $2imes2$ integer matrices. We study the string separation problem for vector automata and demonstrate that generalized finite automata with rational entries can separate any pair of strings using only two states. Investigating stateless homing vector automata, we prove that a language is recognized by stateless blind deterministic real-time version of finite automata with multiplication iff it is commutative and its Parikh image is the set of nonnegative integer solutions to a system of linear homogeneous Diophantine equations.

Recommendations

• Homing vector automata
• Real-time vector automata
• scientific article; zbMATH DE number 1223712
• Language classes associated with automata over matrix groups
• Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition

Cites work

• scientific article; zbMATH DE number 3956447 (Why is no real title available?)
• Affine computation and affine automaton
• Computing with membranes
• EXTENDED FINITE AUTOMATA AND WORD PROBLEMS
• Finite automata over free groups
• Finite automata with multiplication
• Formal Languages and Groups as Memory
• Generalized Automata and Stochastic Languages
• Homing vector automata
• Looking for Pairs that Hard to Separate: A Quantum Approach
• ON STATELESS AUTOMATA AND P SYSTEMS
• On Stateless Deterministic Restarting Automata
• On a conjecture by Christian Choffrut
• On stateless multihead automata: hierarchies and the emptiness problem
• On stochastic languages
• Quantum finite automata: a modern introduction
• Real-time vector automata
• Remarks on blind and partially blind one-way multicounter machines
• Remarks on separating words
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Semigroup automata with rational initial and terminal sets
• Separating strings with small automata
• Superiority of one-way and realtime quantum machines

Cited in

(2)

• Real-time vector automata
• Homing vector automata

This page was built for publication: New results on vector and homing vector automata

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