A Survey of Multi-Tape Automata

2012/05/01 by Carlo A. Furia, Furia, Carlo A. · 9 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Automaton #Computer science #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Theoretical computer science #cs.FL #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1205.0178

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2012/05/01 · arxiv created 2013/11/29 · arxiv updated 2013/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper summarizes the fundamental expressiveness, closure, and decidability properties of various finite-state automata classes with multiple input tapes. It also includes an original algorithm for the intersection of one-way nondeterministic finite-state automata.

Cited by

• Asynchronous Multi-Tape Automata Intersection: Undecidability and Approximation
• Hyper pattern matching

Related

• Asynchronous Multi-Tape Automata Intersection: Undecidability and Approximation
• Revisiting the Equivalence Problem for Finite Multitape Automata
• Multitape automata and finite state transducers with lexicographic weights
• Algorithms for weighted multi-tape automata
• Input-Erasing Two-Way Finite Automata