Title: Generalized Counters and Reversal Complexity
Speaker: Dr. M V Panduranga Rao
Date: November 10, 2008
Abstract:
Deterministic Counter automata are deterministic finite automata enhanced with counters. A counter is a device capable of storing an integer on which three operations can be performed by the finite control: increment, decrement (or do nothing) and test-for-zero.
Two counters can simulate a tape, and therefore a two-counter machine is as powerful as a Turing machine. However, imposing restrictions on resources yields proper subclasses of recursive languages.
A deterministic counter machine could be restricted in terms of different resources like (a) the number of counters it is equipped with, (b) if the head can move both ways on the input tape (if so, how many such head reversals are allowed) and (c) the number of times the counter(s) is allowed to switch between increment and decrement modes (called counter reversal complexity).
Other variants of counter machines also exist in literature. For example, blind counter machines have no information available on the contents and sign of the counters. Partially blind counter machines are also blind; in addition, the contents of the counter must always be non-negative. The machine crashes on being driven below zero.
In this talk, we will explore generalizations of counters. We will introduce a generalization that yields natural definitions for blind and partially blind counter machines and facilitates reversal complexity analysis on them--something that is not possible for straightforward group theoretic generalizations. We will discuss some instances of the generalized counter and a hierarchy in terms of power of language recognition.
About the Speaker:
M V Panduranga Rao did his MTech from department of CSE, IITK and PhD from IISc Bangalore in the area of Quantum Computing. He is working with TRDDC, Pune since then.