scientific article; zbMATH DE number 3911710

From MaRDI portal
Publication:3687716





[For the entire collection see Zbl 0544.00022.] We shall deal with the following three questions concerning the power of alternation in finite automata theory: 1. What is the simplest kind of device for which alternation adds computational power? 2. What are the simplest devices (according to the language family accepted by them) such that the alternating version of these devices is as powerful as Turing machines? 3. Can the number of alternations in the computations of alternating devices be bounded by a function of input word length without loss of the computational power? We give a partial answer to the Questions 1 and 2, i.e. we find the simplest known devices having the required properties according to alternation (multihead simple finite automata and one-way multicounter machines with blind counters respectively). Besides this, considering one-way multicounter machines whose counter contents is bounded by the input word length we find a new characterisation of P (the class of languages accepted by deterministic Turing machines in polynomial time). For one-way alternating multihead finite automata we show that the number of alternations in computations cannot be bounded by \(n^{1/3}\) for input words of length n.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3687716)