Alternating multihead finite automata (Q1116353): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Time and tape complexity of pushdown automaton languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Alternation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5670175 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An observation on time-storage trade off / rank
 
Normal rank
Property / cites work
 
Property / cites work: Propositional dynamic logic of regular programs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198075 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Multi-tape and multi-head pushdown automata / rank
 
Normal rank
Property / cites work
 
Property / cites work: On non-determinacy in simple computing devices / rank
 
Normal rank
Property / cites work
 
Property / cites work: On two-way multihead automata / rank
 
Normal rank
Property / cites work
 
Property / cites work: Space-bounded reducibility among combinatorial problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complete problems for deterministic polynomial time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pushdown automata with counters / rank
 
Normal rank
Property / cites work
 
Property / cites work: Classes of Pebble Games and Complete Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4778268 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Transformational methods and their application to complexity problems. Corrigenda / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3885190 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on two-way nondeterministic pushdown automata / rank
 
Normal rank
Property / cites work
 
Property / cites work: Relating refined space complexity classes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Provably Difficult Combinatorial Games / rank
 
Normal rank
Property / cites work
 
Property / cites work: On tape-bounded complexity classes and multihead finite automata / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4140411 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4142695 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4146255 / rank
 
Normal rank
Property / cites work
 
Property / cites work: <i>k</i> + 1 Heads Are Better than <i>k</i> / rank
 
Normal rank

Latest revision as of 13:16, 19 June 2024

scientific article
Language Label Description Also known as
English
Alternating multihead finite automata
scientific article

    Statements

    Alternating multihead finite automata (English)
    0 references
    0 references
    1988
    0 references
    [See also the review of the preliminary version of this paper, Lect. Notes Comput. Sci. 115, 506-520 (1981; Zbl 0471.68060).] We define alternating multihead finite automata, a generalization of nondeterministic multihead finite automata based on the alternating Turing machine model introduced by \textit{A. K. Chandra}, \textit{D. C. Kozen} and \textit{L. J. Stockmeyer} J. Assoc. Comput. Mach. 28, 114-133 (1981; Zbl 0473.68043). We study the relationships between the classes of languages accepted by alternating multihead finite automata and the classes accepted by deterministic and nondeterministic multihead finite automata and pushdown automata. We also examine basic questions about alternating multihead finite automata (for example, are \(k+1\) heads better than k ?). We conclude by placing upper bounds on the deterministic time and space complexity of the classes of languages accepted by alternating multihead finite automata. As corollaries to our results about alternating multihead finite automata, we obtain several facts about multihead pushdown automata, indicating that the study of alternating multihead finite automata may lead to useful results about nonalternating automata.
    0 references
    alternating Turing machine
    0 references
    nondeterministic multihead finite automata
    0 references
    deterministic time and space complexity
    0 references
    multihead pushdown automata
    0 references
    alternating multihead finite automata
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references