Estudia

• Ser capaç d'estudiar propietats de sistemes de reescriptura, així com de fer demostracions elementals sobre aquestes.
• Ser capaç de reconèixer de quina manera un llenguatge/sistema està relacionat amb la reescriptura.
• Ser capaç de formalitzar i desenvolupar sistemes de reescriptura per a resoldre problemes reals mitjançant programació funcional.

1. Fonaments de la reescriptura

          1.1. Introducció i exemples

          1.2. Reescriptura de primer ordre

                    1.2.1. Termes (contextos, ocurrències, subtermes, termes com a arbres, substitucions, matching, unificació)

                    1.2.2. Sistemes de reescriptura (relacions de reescriptura, formes normals, acabament, confluència local, confluència, monotonia, estabilitat sota substitucions)

                    1.2.3. Sistemes equacionals

                    1.2.4. La reescriptura com a mecanisme deductiu

          1.3. Acabament

                    1.3.1. ordres de reducció

          1.4. Confluència

                    1.4.1. parells crítics

                    1.4.2. lema de Newman

          1.5. Compleció

2. Aplicacions de la reescriptura

          2.1. Tree automata: XML Validation, Typing, Queries

                    2.1.1. Tree automata (binary and unanked trees)

                    2.1.2. DTDs (extended DTDs, one-pass typing)

                    2.1.3. Streaming tree automata

                    2.1.4. Datalog (node selection queries, navigation)

                    2.1.5. MSO (queries, equivalence to tree automata and Datalog)

                    2.1.6. XPath 2.0 and FO

          2.2. Tree transformations

                    2.2.1. XQuery, the XML query language

                    2.2.2. Tree transducers and XSLT

Activitats d'avaluació:

Hi haurà un nota de teoria, amb un pes del 50%, obtinguda mitjançant exercicis proposats durant el curs.

La nota de laboratori (50%) s'obtindrà a partir de l'avaluació de les successives entregues dels exercicis a les classes de laboratori.

També es podrà millorar la nota mitjançant l'estudi i presentació d'algun tema del curs.

Qualsevol tipus de computació pot veure's com a un procés de reescriptura. L'objectiu principal del curs és proporcionar una visió uniforme de diferents sistemes de reescriptura i algunes de les seves aplicacions. En particular es farà èmfasi en l'estudi de les propietats computacionals més interessants d'aquests sistemes, i en la seva aplicació en llenguatges de programació funcionals, tractament de documents XML, ...