The expressive power of existential second order logic with unary functions

Lines connect the coordinator with its partners.

Project objective

Research objectives and content The project concerns the domain of Finite Model Theory. A major issue of this domain is the possibility to define complexity measures (for, say, database queries) by means of the logical resources needed to define a given query, and to use them for a fine analysis of computational complexity classes, such as NP. Here, an investigation of the query classes definable in existential second order logic (that is, NP) with function variables is intended. A first line of research will handle with the hierarchy based on the number of function variables, related to the complexity class nondeterministic linear time. A second line will investigate the monadic theory of square grids, that is existential monadic second order logic with a built-in system of two unary functions. This research could contribute to resolve open problems on the fine structure of NP. Proof methods are Ehrenfeucht-Fraisse games for first order logic with Henkin quantifiers. and finite automata working on grids (instead of words). Training content (objective, benefit and expected impact) This project continues the applicant's actual research, and tries to solve questions left open so far. Two new potential proof methods - automata theory and Henkin quantifiers - are to be considered. Further results can potentially be obtained with their help. Links with industry / industrial relevance (22)

Original text from CORDIS.

Participants

• Technische Universität Wien · WienCoordinatorAustria

Links

• View on CORDIS