Term Rewriting And All That (Baader)

10 flashcards · Mathematics · by lakesare

1. What's equational logic?

   Predicate logic, where the only predicate is equality.

2. What do these two symbols indicate: → VS ≈ ?

   → - we can only rewrite from left ≈ - we can rewrite in both directions

3. When is the initial expression in normal form? Initial expression Rules

   When it can be no further reduced.

4. Visually imagine a confluent rewriting system.

   If different rules can be applied to a given term t, leading to different terms t1 and t2, can t1 and t2 be joined, is there a term s that can be reached from t1 and t2 by rule applications?

5. How can we regain confluence? Initial expression Rules

6. What's a total function?

   A function which is defined for all inputs of the right type, that is, for all of a domain.

7. Visually imagine a word problem.

   Given terms e and x◦i(x), can they be rewritten into each other?

8. What grammars do I already know?

   Regular Grammar (== finite-state automata) Context-Free Grammar (== pushdown automata) Regular expression is a compact notation for regular grammars.

9. Visually imagine the Chomsky hierarchy. (aka Chomsky–Schützenberger hierarchy) Noam Chomsky

   In formal language theory, computer science and linguistics, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars. This hierarchy of grammars was described by Noam Chomsky in 1956.

10. What does ARS stand for?

    Abstract Reduction System