Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
sav08:homework08 [2008/09/13 23:59] vkuncak |
sav08:homework08 [2008/09/15 15:22] vkuncak |
||
|---|---|---|---|
| Line 23: | Line 23: | ||
| \] | \] | ||
| By generalizing the objective function to reals, we can solve non-linear but polynomial optimization problems using quantifier elimination over reals. | By generalizing the objective function to reals, we can solve non-linear but polynomial optimization problems using quantifier elimination over reals. | ||
| + | |||
| ===== Problem 2 ===== | ===== Problem 2 ===== | ||
| Line 41: | Line 42: | ||
| Added afterwards: | Added afterwards: | ||
| + | * {{sav08:laeuchlileonard66linearorder.pdf|Läuchli, H., Leonard, J.: On the elementary theory of linear order. Fund. Math. 59, 109–116 (1966)}} (Thanks to Yuri Gurevich, who also mentions that result follows from decidability of S2S) | ||
| + | * [[http://www.jstor.org/sici?sici=0022-4812%28196806%2933%3A2%3C287%3AOTETOL%3E2%2E0%2ECO%3B2-I&origin=euclid|review]], {{sav08:review-linearorder.pdf|review pdf}} | ||
| + | |||
| * {{sav08:ehrenfeuchtordergames.pdf|A. Ehrenfeucht. An application of games to the completeness problem for formalized theories}}. Fund. Math., 49:129–141, 1961. | * {{sav08:ehrenfeuchtordergames.pdf|A. Ehrenfeucht. An application of games to the completeness problem for formalized theories}}. Fund. Math., 49:129–141, 1961. | ||
| * {{sav08:gurevich-thesis.pdf|Y. Gurevich: Elementary Properties of Ordered Abelian Groups}} | * {{sav08:gurevich-thesis.pdf|Y. Gurevich: Elementary Properties of Ordered Abelian Groups}} | ||
| Line 46: | Line 50: | ||
| * {{sav08:shelah-order.pdf|S. Shelah: The Monadic Theory of Order}} | * {{sav08:shelah-order.pdf|S. Shelah: The Monadic Theory of Order}} | ||
| * [[http://dx.doi.org/10.1016/0304-3975(95)00221-9|Françoise Maurin: Exact Complexity Bounds for Ordinal Addition. Theor. Comput. Sci. 165(2): 247-273 (1996)]] | * [[http://dx.doi.org/10.1016/0304-3975(95)00221-9|Françoise Maurin: Exact Complexity Bounds for Ordinal Addition. Theor. Comput. Sci. 165(2): 247-273 (1996)]] | ||
| + | * Françoise Maurin, Ehrenfeucht games and ordinal addition, 1998. (We show in this paper that the theory of ordinal addition of any fixed ordinal ω^α, with α less than ω^ω, admits a quantifier elimination. This in particular gives a new proof for the decidability result first established in 1965 by R. Büchi using transfinite automata. Our proof is based on the Ehrenfeucht games, and we show that quantifier elimination go through generalized power. | ||
| + | |||