No label defined (Q4237287)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1272994
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1272994

      Statements

      0 references
      5 April 1999
      0 references
      finite model theory
      0 references
      descriptive complexity theory
      0 references
      complexity theory
      0 references
      reducibilities
      0 references
      oracle Turing machines
      0 references
      capturing of relativized complexity classes
      0 references
      relativized model of computation
      0 references
      oracle sets
      0 references
      Lindström quantifier
      0 references
      Given some appropriate representation of finite models by binary strings, we say a logic \(\mathcal L\) captures a complexity class \(\mathcal C\) iff every language in \(\mathcal C\) corresponds to a class of finite models of a sentence over \(\mathcal L\) and, conversely, the set of representations of such a model class is always in \(\mathcal C\). (For background see the textbooks of \textit{H.-D. Ebbinghaus} and \textit{J. Flum} [Finite model theory (1995; Zbl 0841.03014)] and of \textit{N. Immerman} [Descriptive complexity (1999; Zbl 0918.68031)].) The thesis is about the capturing of relativized complexity classes, i.e., given a relativized model of computation one wants to specify for all oracle sets \(A\), a logic \({\mathcal L}^A\) which captures the class determined by the computation model and \(A\). Here it is required that the logic \({\mathcal L}^A\) depends on \(A\) only insofar as its formulas might contain a Lindström quantifier which is canonically derived from \(A\). After introducing some basic concepts from finite model theory and complexity theory, the author reviews several models of computations with oracles as introduced by \textit{T. Baker, J. Gill}, and \textit{R. Solovay} [SIAM J. Comput. 4, 431-442 (1975; Zbl 0323.68033)], \textit{R. E. Ladner} and \textit{N. A. Lynch} [Math. Syst. Theory 10, 19-32 (1976; Zbl 0341.68036)], \textit{J. Simon} [On some subrecursive reducibilities, Ph.D. dissertation, Stanford University (1977)], \textit{W. L. Ruzzo, J. Simon}, and \textit{M. Tompa} [J. Comput. Syst. Sci. 28, 216-230 (1984; Zbl 0573.68021)], \textit{C. B. Wilson} [Lect. Notes Comput. Sci. 223, 362-382 (1986; Zbl 0615.68039)], \textit{J. F. Buss} [J. Comput. Syst. Sci. 36, 351-378 (1988; Zbl 0657.68047)], \textit{J. A. Makowsky} and \textit{Y. B. Pnueli} [Lect. Notes Comput. Sci. 832, 189-222 (1994)], \textit{Frick} [Thesis, Univ. Freiburg (1996)], as well as previous work on capturing relativized complexity classes by \textit{E. Grädel} [Lect. Notes Comput. Sci. 440, 163-175 (1990)], \textit{I. A. Stewart} [Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. 18, 65-92 (1993; Zbl 0782.68049); Lect. Notes Comput. Sci. 832, 318-333 (1994)], \textit{H. Imhof} [J. Log. Comput. 7, 405-425 (1997; Zbl 0880.03012); Fixed point logics and generalized quantifiers in descriptive complexity, Thesis, Univ. Freiburg (1996; Zbl 0870.03015)], \textit{Y. B. Pnueli} [unpublished manuscript, 1994], and Frick (see above). The remaining parts of the thesis focus on the capturing of relativized classes which correspond to the various models of oracle Turing machines which run in alternating polynomial time, nondeterministic logarithmic space, or deterministic polynomial space.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references