Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:homework08 [2008/09/15 15:22] vkuncak |
sav08:homework08 [2008/09/17 23:03] vkuncak |
||
|---|---|---|---|
| Line 41: | Line 41: | ||
| If you cannot solve the problem in its entirety, write observations that you could obtain. You are allowed (but not required) to use any references (books, papers) that you can find (but it may be easier to solve the problem on your own). You must cite any references that you used. You need not write down in great detail explanations of simple facts, but if you omit any proof steps make sure that they indeed simple. | If you cannot solve the problem in its entirety, write observations that you could obtain. You are allowed (but not required) to use any references (books, papers) that you can find (but it may be easier to solve the problem on your own). You must cite any references that you used. You need not write down in great detail explanations of simple facts, but if you omit any proof steps make sure that they indeed simple. | ||
| - | Added afterwards: | + | Solution (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) | + | * {{sav08:laeuchlileonard66linearorder.pdf|Läuchli, H., Leonard, J.: On the elementary theory of linear order. Fund. Math. 59, 109–116 (1966)}} |
| - | * [[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:rabin69s2s.pdf|Decidability of Second-Order Theories and Automata on Infinite Trees, by Michael O. Rabin}} |
| + | Somewhat related papers: | ||
| * {{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}} | ||