Structuur thesistekst

Gezien de literatuurstudie grotendeels achter de rug is, wordt het tijd de opgedane kennis te verwerken en in eigen woorden te structureren.

Het eerste gedeelte zal definities en concepten omschrijven die als voorkennis beschouwd worden. Ook veelgebruikte notaties zullen hierin besproken worden. Gebruikte concepten zullen zijn: bomen, algebra's, relaties, ...

Vervolgens zullen eindige automaten behandeld worden. Hiertoe behoren zowel deterministische als niet-deterministische automaten. Ook de minimisatie van deze modellen alsook het Myhill-Nerode theorema komen ter sprake.

De volgende stap is die van de boomautomaten. Naast de omschrijving van dit concept zullen ook hier het Myhill-Nerode theorema en de minimisatie een plaats vinden.

Tot slot zal er gesproken worden over automaten op unranked boomautomaten. De minimisatie hiervan zal enkele problemen scheppen. Een algemene vorm van een boom kan geëncodeerd worden tot een ranked boom, bijvoorbeeld door het gebruiken van de extensie-operator @. Dankzij deze encodering wordt het mogelijk om doormiddel van stapsgewijze automaten toch een unieke minimisatie te bekomen. Deze techniek zal in het tweede gedeelte van de thesis verder onderzocht worden.

Opzet van de thesis

Eindige automaten die als input een string aanvaarden, kunnen geminimiseerd worden naar een automaat met het minimum aantal toestanden die nodig zijn om dezelfde taal te aanvaarden.

Naast automaten op strings bestaan er ook automaten op boomstructuren, hetgeen vooral interessant is in de context van XML. XML is op zich een boomstructuur. Ook deze automaten kunnen geminimiseerd worden hoewel dit niet even duidelijk is als bij string-automaten.

In deze thesis zal eerst onderzoek uitgevoerd worden naar boomautomaten en het minimiseren hiervan. Hier dient in eigen woorden een tekst over geschreven te worden.

In het tweede deel zal er een nieuwe manier onderzocht worden die de UHasselt samen met Franse onderzoekers ontdekt heeft.