• English only

# Differences

This shows you the differences between two versions of the page.

 sav08:evaluating_formulas_in_finite_structures [2008/03/19 10:41]vkuncak sav08:evaluating_formulas_in_finite_structures [2008/03/19 15:23] (current)vkuncak Both sides previous revision Previous revision 2008/03/19 15:23 vkuncak 2008/03/19 10:41 vkuncak 2008/03/19 00:46 vkuncak 2008/03/19 00:45 vkuncak 2008/03/19 00:39 vkuncak 2008/03/19 00:37 vkuncak 2008/03/19 00:36 vkuncak 2008/03/18 19:18 vkuncak 2008/03/18 19:12 vkuncak 2008/03/18 19:08 vkuncak created 2008/03/19 15:23 vkuncak 2008/03/19 10:41 vkuncak 2008/03/19 00:46 vkuncak 2008/03/19 00:45 vkuncak 2008/03/19 00:39 vkuncak 2008/03/19 00:37 vkuncak 2008/03/19 00:36 vkuncak 2008/03/18 19:18 vkuncak 2008/03/18 19:12 vkuncak 2008/03/18 19:08 vkuncak created Line 30: Line 30: Given a language ${\cal L}$, formula a formula $F$ in ${\cal L}$ and an interpretation $I=(D,​\alpha)$,​ determine $e_F(F)(I)$. Given a language ${\cal L}$, formula a formula $F$ in ${\cal L}$ and an interpretation $I=(D,​\alpha)$,​ determine $e_F(F)(I)$. - Basic idea: iterate over all domain elements ​for quantifiers. + Basic idea: to evaluate quantifiers, ​iterate over all domain elements. - + - * fix formula: LOGSPACE (number of vars fixed, number of their bits changes) + - * fix language with symbols of bounded arity: PSPACE (number of variables increases with formula size, see also [[QBF and Quantifier Elimination|QBF]]) + + * fix formula, change domain size $|D|$: LOGSPACE (number of vars fixed, number of their bits changes) + * fix language with symbols of bounded arity, change formula: PSPACE (number of variables increases with formula size, see also [[QBF and Quantifier Elimination|QBF]]) ===== References ===== ===== References =====

sav08/evaluating_formulas_in_finite_structures.txt · Last modified: 2008/03/19 15:23 by vkuncak

© EPFL 2018 - Legal notice