scientific article; zbMATH DE number 3911710
[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.
- On the power of alternation in automata theory
- On the power of P automata
- On the power of input-synchronized alternating finite automata
- On computational power of weighted finite automata
- scientific article; zbMATH DE number 871243
- On the computational power of affine automata
- An alternating hierarchy for finite automata
- On the power of P and dP automata
- On alternating \(\omega\)-automata
- On the power of alternation on reversal-bounded alternating Turing machines with a restriction
- Alternating simple multihead finite automata
- Alternating multicounter machines with constant number of reversals
- On the power of alternation in automata theory
- Alternating multihead finite automata
- Alternation with a pebble
- On the power of alternation on reversal-bounded alternating Turing machines with a restriction
- Square on deterministic, alternating, and Boolean finite automata
- One alternation can be more powerful than randomization in small and fast two-way finite automata
- scientific article; zbMATH DE number 4094826 (Why is no real title available?)
- An alternating hierarchy for finite automata
- scientific article; zbMATH DE number 3999320 (Why is no real title available?)
- scientific article; zbMATH DE number 862672 (Why is no real title available?)
- Gaining Power by Input Operations: Finite Automata and Beyond
- Square on Deterministic, Alternating, and Boolean Finite Automata
- On emptiness and counting for alternating finite automata
- Fuzzy alternating automata over distributive lattices
- Alternating finite automata with limited universal branching
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)