Estudia > Oferta formativa > Oferta d'assignatures > Detall de l'assignatura
Anar al contingut (clic a Intro)
UdG Home UdG Home
UdG 30 anys
Tancar
Menú

Estudia a la UdG

Dades generals

Curs acadèmic:
2008
Descripció:
Sistemes de reescriptura. Autòmats d'arbre. Consultes, validació i tipatge de documents XML.
Crèdits:
5
Idioma principal de les classes:
Anglès
S’utilitza oralment la llengua anglesa en l'assignatura:
Indistintament (50%)
S’utilitzen documents en llengua anglesa:
Majoritàriament (75%)

Grups

Grup A

Durada:
Anual
Professorat:
Miquel Bofill Arasa  / Mateu Villaret Auselle

Altres Competències

  • 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.

Continguts

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

Tipus d’activitat Hores amb professor Hores sense professor Total
Total 0 0 0

Bibliografia

    Avaluació i qualificació

    Activitats d'avaluació:

    Descripció de l'activitat Avaluació de l'activitat %

    Qualificació

    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.

    Observacions

    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, ...

    Escull quins tipus de galetes acceptes que el web de la Universitat de Girona pugui guardar en el teu navegador.

    Les imprescindibles per facilitar la vostra connexió. No hi ha opció d'inhabilitar-les, atès que són les necessàries pel funcionament del lloc web.

    Permeten recordar les vostres opcions (per exemple llengua o regió des de la qual accediu), per tal de proporcionar-vos serveis avançats.

    Proporcionen informació estadística i permeten millorar els serveis. Utilitzem cookies de Google Analytics que podeu desactivar instal·lant-vos aquest plugin.

    Per a oferir continguts publicitaris relacionats amb els interessos de l'usuari, bé directament, bé per mitjà de tercers (“adservers”). Cal activar-les si vols veure els vídeos de Youtube incrustats en el web de la Universitat de Girona.