Hoppa direkt till innehållet
printicon

Transformation av komplexa strukturer: Teori och implementering

Forskningsprojekt Inom projektet bedrivs i första hand grundforskning som fokuserar på system som genererar och transformerar komplexa datastrukturer såsom matematiska träd, grafer och bilder. Både teorin för sådana system och deras implementering behandlas.

Målsättningen är att vidareutveckla teorin och förbättra förutsättningarna för praktisk tillämpning. Grafer spelar en viktig roll när det gäller att modellera fysiska eller logiska system. Till exempel representeras programvara som grafer i alla moderna verktyg för programvaruutveckling. Träd spelar en minst lika viktig roll, t.ex. i tillämpningar som har med XML, standarden för webbdokument, att göra. Ett annat exempel är tillämpningar inom människo-dator-interaktion som syftar till att kunna kommunicera med datorn på naturligt språk. Där förekommer träd bl.a. i form av syntaxträd som delar upp meningar i subjekt, predikat, objekt o.s.v.

Projektöversikt

Projektperiod

2007-01-01 2009-12-31

Forskningsämne

Datavetenskap

Projektbeskrivning

Projektet fokuserar på delområden inom teoretisk datalogi som undersöker system för att generera och transformera komplexa objekt, i synnerhet (a) träd, (b) grafer och (c) bilder.

Område (a) handlar om system som genererar eller transformerar (matematiska) träd, en teori som skapades omkring 1970 i samband med forskning på syntaxstyrd översättning av programspråk. Nyare användningsområden inkluderar bildgenerering, vilket är ett viktigt resultat av det här projektet som bl.a. har lett till en monografi och lärobok (se [16] i publiceringslistan). Boken är den första som ger en systematisk presentation av stora delar av området.

Under (b) undersöks system som transformerar grafer med hjälp av lokala regler, vilket är viktigt p.g.a. den centrala rollen grafer spelar i ämnet datavetenskap. Forskningen ämnar bl.a. vidareutveckla en ny grammatiktyp (adaptive star grammar) som har tillämpningar inom området software refactoring.

Område (c) handlar om system som genererar bilder. Det centrala begreppet är trädbaserad bildgenerering (se ovan). Ett viktigt mål på det här delområdet är att etablera en avancerad typ av grammatik som genererar så kallade progressiva scener.

Forskningsarbetet sker i samarbete med kollegor i Australien, Belgien, Holland, Sydafrika och Tyskland.