Multitape one-way nonwriting automata

DOI10.1016/S0022-0000(68)80028-5zbMath0159.01504OpenAlexW2094082874MaRDI QIDQ2527943

Patrick C. Fischer, Arnold L. Rosenberg

Publication date: 1968

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(68)80028-5

zbMATH Keywords

mathematical logic

Related Items (40)

Two-way non-uniform finite automata ⋮ Unnamed Item ⋮ Rational equivalence relations ⋮ The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ Hierarchies of one-way multihead automata languages ⋮ Quasi-automatic semigroups ⋮ Determinism and Nondeterminism in Finite Automata with Advice ⋮ Two-Way Non-Uniform Finite Automata ⋮ New techniques for proving the decidability of equivalence problem ⋮ On the representation of finite deterministic 2-tape automata ⋮ On the Decidability of the Equivalence for k-Valued Transducers ⋮ Multihead one-way finite automata ⋮ On the decidability of the equivalence problem for partially commutative rational power series ⋮ Synchronized rational relations of finite and infinite words ⋮ Sequential? ⋮ Abstract families of relations ⋮ The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata ⋮ Marker automata ⋮ Restricted one-counter machines with undecidable universe problems ⋮ Unnamed Item ⋮ Finite automata with multiplication ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Learners based on transducers ⋮ An Automata Theoretic Approach to Rational Tree Relations ⋮ Transducing reversibly with finite state machines ⋮ Both Ways Rational Functions ⋮ On the Decidability of the Equivalence for a Certain Class of Transducers ⋮ Small overlap monoids. II: Automatic structures and normal forms. ⋮ On Synthesis of Resynchronizers for Transducers ⋮ Finite-turn checking automata ⋮ Automata and rational expressions ⋮ Finite transducers and rational transductions ⋮ Decision problems among the main subfamilies of rational relations ⋮ Limitedness theorem on finite automata with distance functions: An algebraic proof ⋮ Modelization of deterministic rational relations ⋮ On the power of synchronization in parallel computations

Cites Work

• Unnamed Item
• Tape-reversal bounded Turing machine computations
• On the Computational Complexity of Algorithms
• Turing machines with a schedule to keep
• On Formalisms for Turing Machines
• A Machine-Independent Theory of the Complexity of Recursive Functions
• One-tape, off-line Turing machine computations

This page was built for publication: Multitape one-way nonwriting automata