Open Access

On Computational Power of Partially Blind Automata

   | Aug 13, 2012

Cite

Baker, B., Book, R.: Reversal-bounded multipushdown machines. Journal of Computer and System Sciences, 8(1974), 315-332.Search in Google Scholar

Greibach, S.: Remarks on the complexity of nondeterministic counter languages, Theoretical Computer Science, 1(1976), 269-288.10.1016/0304-3975(76)90072-4Search in Google Scholar

Harrison, M., Ibarra, O.: Multi-tape and multi-heads pushdown automata. Information and Control, 13(1968), 433-470.Search in Google Scholar

Hopcroft, J., Ullman, J.: Introduction to Automata, Formal Languages and Theory of Computation, Addision-Wesley, Inc. Reading, MA (1979).Search in Google Scholar

Ibarra, O.: Reversal -bounded counter machines and their decision problems, Journal of the ACM, 25(1), (1978).Search in Google Scholar

Ibarra, O., Ravikumar, B.: On partially blind multihead finite automata, Theoretical Computer Science, 365(1), (2006), 190-199.Search in Google Scholar

Jenner, B.: Knapsack problems for NL, Information Processing Letters, 54(3), (1995), 169-174.Search in Google Scholar

Sudborough, I.: A note on tape-bounded complexity clases and linear contex-free languages, Journal of the ACM, 22(4), (1975), 499-500.Search in Google Scholar

Yao, A., Rivest, R.: k+1 heads are better than k, Journal of the ACM, 25(2), (1978), 337-340.Search in Google Scholar

ISSN:
1336-9180
Language:
English