\documentclass[a4paper,12pt]{article}
\usepackage{mathptmx,amsmath,amssymb,fullpage}
\begin{document}
\title{Automata on Infinite Objects, Monadic Theories and Complexity}
\author{A.~Muchnik, A.L.~Semenov (Moscow)}
\date{January 6--10, 1992}

\maketitle
A survey of results obtained by the Mathematical Logic and Computer Science Group at the Institute of New Technologies (Moscow and St.~Petersburg) is presented. The results belong to Konstantin Gorbunov, Andrei Muchnik, Alexei Semenov, Anatol' Slisenko, Sergey Soprunov. Some of the results were proved in parallel with Western research.

Major topics are the following. Conditions of decidability for the monadic theory of a structure $\langle \omega, \le, P\rangle$ where $P$ is an unary predicate (or a tuple of unary predicates). Almost periodic $\omega$-words $P$ and the corresponding monadic theories. Double infinite words. The Muchnik proof of Rabin Theorem. A generalization of Shelah--Stupp Theorem bby adding the unary predicate of equality of two last symbols in a sequence. The uniformization problem in different monadic theories. The complexity of complementation and determinization operations. Arbitrary graphs, their combinatorial properties, new bounds, connections with complexity for finite graphs and decidability for infinite [ones]. An example of predicate on tree for which the weak monadic theory is decidable and the monadic theory is undecidable. Non-existence of a maximal decidable weak monadic theory.

Some of the results wer discussed in Semenov's paper at MFCS'84 (Springer Lecture Notes in Computer Science) and some were proved in Semenov's [paper published in] 
Math. USSR Izvestija, 1984.

(Published in: Kevin Compton, Jean-Eric Pin, Wolfgang Thomas (editors): \textbf{Automata Theory: Infinite Computations}. Dagstuhl-Seminar-Report; 28. 6-10.1.92 (9202). From the Editors' Preface: \ldots Since about thirty years, and important application of finite automata has been their use in the study of monadic second-order theories. These and related logical aspects were treated in talks collected in the fourth session below. A.L.~Semenov and An.A.~Muchnik gave a survey of Russian work on this subject, concerning extension of B\"uchi's successor arithmetic and a strengthening of Rabin's decidability result for the monadic theorey of the infinite binary tree. $\langle\ldots\rangle$ The talks were supplemented by lively discussions, joint work in small groups, and three long night sessions: On Tuesday evening, A.~Muchnik presented his extension of the Shalah--Stupp Theorem (showing that the tree unraveling of a structure has a decidable monadic theory if the given structure has)\ldots

\end{document}
