Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | Next revision Both sides next revision | ||
sav08:logic_and_automata_introduction [2008/05/14 10:10] vkuncak |
sav08:logic_and_automata_introduction [2008/05/14 10:12] vkuncak |
||
---|---|---|---|
Line 25: | Line 25: | ||
Resulting relation for $F(z)$ is $\{ 6k + 5 \mid k \in \mathbb{Z} \}$ | Resulting relation for $F(z)$ is $\{ 6k + 5 \mid k \in \mathbb{Z} \}$ | ||
++++ | ++++ | ||
+ | |||
+ | We need a nice //representation// of relations | ||
+ | * in quantifier elimination these are particular quantifier-free formulas | ||
+ | * in automata-based methods that we will look at, we represent relations as regular languages | ||
In [[Lecture15]] we have seen that Presburger arithmetic is decidable using quantifier elimination. | In [[Lecture15]] we have seen that Presburger arithmetic is decidable using quantifier elimination. | ||
- | Today we look at a different decision method for Presburger arithmetic, which generalizes to certain more expressive logics (monadic second-order logic over strings and trees). | + | Today we see an alternative decision method, based on Presburger arithmetic, and then generalize it to more expressive logics: monadic second-order logic over strings and trees. |