Differences

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

--- sav08:simple_qe_for_dense_linear_orders [2008/04/22 16:33]
piskac
+++ sav08:simple_qe_for_dense_linear_orders [2009/04/22 12:08]
vkuncak
@@ Line 1: / Line 1: @@
 ====== Simple QE for Dense Linear Orders ======
-Example of dense linear order: rational numbers with less-than relation.  Also, real numbers with less-than relation.
+Example of dense linear order: rational numbers with less-than relation.  (It works in the same way for real numbers with less-than relation.)
 ===== Theory of Dense Linear Orders =====
-Language ${\cal L} = \{ < \}$.
+Language ${\cal L} = \{ < \}$.  Atomic formulas are of two forms:
+  * $x=y$
+  * $x < y$
+Literals are either atomic formulas or their negations.
-Formulas are formulas true in structure $(\mathbb{Q},<)$ for all values of free variables.
+Formulas $T$ are the formulas that are closed formulas that are true in the structure $(\mathbb{Q},<)$ or rational numbers.
+**Example:** The 'successor' formula:
+\[
+   \forall x. \exists y.\ x < y \ \land\ (\forall z. (x < z \rightarrow z=y \lor y < z)
+\]
+Is this formula true in dense linear orders? Is there a non-dense linear order where its truth value is different?
 ===== Normal form of Formulas =====
+We have seen that it suffices to eliminate quantifiers from conjunctions of literals.
+Can we assume that literals are of a special form?
+**Example:** simplify these formulas:
+  * $x < y\ \land\ \lnot (y < z) \ \land\ (x \neq z)$
+  * $x < y\ \land y < x$
+If we have three concrete values for $x,y,z$, what is the form of the strongest type of a formula that we could write about them in this language? //(atomic type formula)//
+Theorem: every quantifier-free formula in a language with only relational symbols is a disjunction of atomic type formulas
+  * if we know the set $T$ of axioms, we may be able to show that the atomic type formulas have a simple form
 ===== Quantifier Elimination Step =====
+Quantifier elimination from atomic type formulas:
+Quantifier elimination from more general formulas:
+**Example:** Use quantifier elimination to compute the truth value in dense linear orders for the example 'successor' formula above.
+===== References =====
-  * [[http://www4.informatik.tu-muenchen.de/~nipkow/pubs/lqe.pdf|Linear Quantifier Elimination]]
+  * [[http://www4.informatik.tu-muenchen.de/~nipkow/pubs/lqe.pdf|Linear Quantifier Elimination]] (Tobias Nipkow, IJCAR 2008)
   * [[http://citeseer.ist.psu.edu/loos93applying.html|Applying Linear Quantifier Elimination]]
   * [[http://citeseer.ist.psu.edu/71579.html|Parallel Fourier-Motzkin Elimination]]