A note on the reduction of two-way automata to one-way automata
type: Item
instance of: scholarly article
title: A note on the reduction of two-way automata to one-way automata
zbMATH Open document ID: 0665.68045
DOI: 10.1016/0020-0190(89)90205-6
author: Moshe Y. Vardi
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: We describe a new elementary reduction of two-way automata to one-way automata. The reduction is based on the subset construction rather than on crossing sequence analysis.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4088939
zbMATH Keywords: regular language
zbMATH Keywords: two-way automata
zbMATH Keywords: one-way automata
Wikidata QID: Q57380757
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90205-6
OpenAlex ID: W1977193848
cites work: Q5592246
cites work: Q5541339
cites work: Q5541340
cites work: Nondeterminism and the size of two way finite automata
Recommended article: Q5747095
Recommended article: Q4986301
Recommended article: Remarks on two-way automata with weak-counters
Recommended article: Q3742753
Recommended article: Q4785462
Recommended article: Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
Recommended article: Converting two-way nondeterministic unary automata into simpler automata.
Recommended article: On two-way nondeterministic finite automata with one reversal-bounded counter
Recommended article: Two-way automata and length-preserving homomorphisms
Recommended article: A note on two-way probabilistic automata
description: scientific article; zbMATH DE number 4088939