Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation (Q1822982): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(89)90154-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2050997354 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A space-hierarchy result on two-dimensional alternating Turing machines with only universal states / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some properties of two-dimensional on-line tessellation acceptors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Two-dimensional alternative Turing machines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on three-way two dimensional alternating Turing machines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Two-dimensional alternating turing machines with only universal states / rank | |||
Normal rank |
Latest revision as of 09:33, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation |
scientific article |
Statements
Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation (English)
0 references
1989
0 references
A two-way two-dimensional alternating finite automaton (TW2-AFA) is a two-dimensional alternating finite automaton [see the second and third author with \textit{H. Taniguchi}; Theor. Comput. Sci. 27, 61-83 (1983; Zbl 0539.68039)] whose input head can move right and down (or may not move). A two-dimensional deterministic on-line tesselation acceptor (2-dota) is a two-dimensional on-line tesselation acceptor [see the second author and \textit{A. Nakamura}; Inform. Sci. 13, 95-121 (1977; Zbl 0371.94067)] whose the cell state function is a singleton. It is proved that 2-dota's are equivalent to TW2-AFA's through 180\(\circ\)-rotation.
0 references
tessellation acceptors
0 references
finite automata
0 references
equivalence
0 references
0 references