Role of determinism in query languages for data bases (Q1112628)

The idea of using a predicate logic as a query language for data bases belongs to \textit{E. F. Codd} and has existed for a long time. Relatively recently \textit{A. Chandra} and \textit{D. Harel} [J. Comput. Syst. Sci. 25, 99-128 (1982; Zbl 0511.68073)], considered a hierarchy of more powerful languages for data bases. Languages of various dynamic logics can be used as such languages as well. A natural requirement of such languages - the existence of an algorithm for determination of the truth of a given formula on a given data base - does not allow the use of certain powerful logics, for example a recursively enumerable logic. It is interesting in this connection to compare the expressive power of the languages of regular (DL) and deterministic regular (DDL) logics as query languages for data bases [see definitions in (*)\ \textit{M. A. Tajtslin}, Sib. Mat. Zh. 24, No.3(139), 184-192 (1983; Zbl 0518.03002)]. This is equivalent to a comparison of DDL and DL on the class of finite structures. The problem of the relation of the expressive power of DDL and DL is found in many works [\textit{A. R. Meyer} and \textit{K. Winklmann}, Theor. Comput. Sci. 18, 301-323 (1982; Zbl 0478.68031), et al.]. The answer was obtained by \textit{A. P. Stolboushkin} and \textit{M. A. Tajtslin} [ibid. 27, 197-209 (1983; Zbl 0536.03015)], as well as by \textit{P. Bernau}, \textit{J. Y. Halpern} and \textit{J. Tiuryn} [(**)\ Lect. Notes Comput. Sci. 140, 48-60 (1982; Zbl 0494.68032)]. However, in these works DDL and DL differ on classes of infinite structures. Our goal is to show that DL and DDL differ on the class of finite structures. In this connection we shall use techniques from (**). In addition, we assume familiarity with (*), in order not to repeat the definitions of DL and DDL. We note that in (*) DL is denoted by L(RG,0) and DDL by L(RD,0).