New results on vector and homing vector automata

DOI10.1142/S0129054119500291zbMATH Open1427.68154arXiv1905.11857OpenAlexW3003657000MaRDI QIDQ5207237FDOQ5207237

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)

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.

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

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

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)

Cites Work

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

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)