Input-driven pushdown automata (IDPDA), also called visibly pushdown automata (VPA), are one of the simplest and most successful models in automata theory: it allows you to analyze nested constructs, and then however, in many applications they can be used with the same ease as finite machines.
Input-driven automata are a special case of ordinary pushdown automata, with the restriction that for each character of the input alphabet one of three types is specified, which predetermines the operation on the stack when reading this character: on the opening brackets, the automaton must place one stack character on the top of the stack; on closing brackets 鈥� pop one character from the stack; and on neutral symbols the automaton cannot access the stack at all.
A number of key results on input-controlled automata were obtained back in the early 1980s: it is known that the non-deterministic version of these automata (NIDPDA) can be deterministic, and any language recognized by such an automaton lies in the complexity class L, that is, it can be recognized a Turing machine using log n memory, wh ere n is the length of the input string. In the early 2000s, many new results were obtained about this model. New varieties of these automata were considered: in particular, IDPDA working with infinite strings, used as a program verification model, unambiguous NIDPDA, real-time IDPDA, and others.
The proposed two lectures will retell the main results on the properties of this important and interesting model.
