On June 16鈥�17, MCA hosted open lectures by , Professor of the Department of Mathematics and Computer Science of St. Petersburg State University.
The lectures gave a detailed overview of the main findings about input-driven pushdown automata (IDPDA). The IDPDA model allows for fine analysis of nested constructs, and in many applications IDPDA can be applied with the same ease as conventional state machines.
Within the framework of the lectures, the determination algorithm for non-deterministic IDPDAs was discussed. Exact estimates of the complexity of the void problem for IDPDA were derived: this problem is P-complete for deterministic automata and EXP-complete in the non-deterministic case. Also shown are estimates for the number of states required by these automata to represent basic operations on languages.
A. S. Okhotin's lectures were organized by MCA staff members Viktor Selivanov and .
Nikolay Bazhenov says:
With the support of MCA, research is being conducted on the subrecursive complexity of algebraic structures: in particular, polynomially computable structures and structures representable by means of finite automata are investigated. A. S. Okhotin is a leading specialist in the theory of automata and formal grammars. His lectures provide an overview of important results on the algorithmic complexity of various problems for IDPDA. For my part, I want to especially note the remarkable structuredness of the lectures given: despite the general complexity of the presented material, the presentation is made available for students who have mastered the basic course of the theory of algorithms.
