Některé otázky reprezentace času

Některé otázky reprezentace času Daniela Ponce Univerzita Hradec Králové, Rokitanského 62, Hradec Králové 500 03 E-mail: [email protected] Abstrakt. Příspěvek se zabývá základními otázkami reprezentace času a časového uvažování. Pozornost je též věnována granularitě času, jejím vlastnostem a způsobům reprezentace, jakož i systémům granularit.

1 Úvod Reprezentace času a časové uvažování se zabývá jedním ze základních problémů umělé inteligence, protože čas je neoddělitelnou dimenzí světa, který nás obklopuje, a časový aspekt je nezbytný při uvažování o změnách, které se ve světě dějí a o činech, kterými do tohoto světa zasahujeme. Bez zohlednění časového aspektu je prakticky nemožné řešit problémy inteligentním způsobem.

2 Ontologie času Reprezentaci času můžeme začít otázkou, jakou základní stavební jednotku času zvolit. Následně nás bude zajímat, do jaké struktury uspořádáme stavební jednotky času a jaké budeme konstruovat časové vztahy a výrazy. Důležitá je též volba nástroje, který nám umožní uvažování o tvrzeních vymezených v čase. 2.1 Základní stavební jednotky času a časové entity Za základní stavební jednotku času můžeme považovat okamžik (bod v čase, [28], [29]) a časový interval ([2], [3]). Každá z těchto možností má své opodstatnění. V běžném uvažování považujeme za okamžité některé změny stavu světa z jednoho do jiného, kupř. rozsvícení lampy s běžnou žárovkou ([35]). Změnu temné místnosti na osvětlenou vnímáme v tomto případě jako okamžitou. Jiný je případ lampy se zářivkou, kde rozsvícení úsporné žárovky není okamžité a od otočení zapínačem trvá nějaký čas (časový interval) než lampa svítí plnou intenzitou. Jako časový interval vnímáme též trvání vlastnosti (stůl je těžký) nebo uskutečnění procesu (namalování obrazu) či události (oslava narozenin). Některé teorie používají jako základní stavební jednotky času jak okamžik, tak časový interval (kupř. [38]). Hlavní časové entity jsou fakt a událost. Pod faktem rozumíme věc (tvrzení), která je platná v čase. Jedná se o statický aspekt světa. Fakt časově vymezujeme vzhledem k nějakému okamžiku (kupř. zůstatek na účtu k poslednímu dni měsíce) nebo k časovému intervalu (kupř. nemocný chřipkou po dobu dvou týdnů). Událost je věc, která se děje v čase (kupř. příprava přednášky). Jedná se o dynamický aspekt světa. Události časově vymezujeme vzhledem k časovému intervalu.

2.2 Struktura času Strukturu času můžeme vymezit určením následujících dimenzí ([35]). Diskrétní nebo spojitá povaha času. Volba mezi diskrétní a spojitou povahou času záleží na charakteru časových entit, které chceme reprezentovat. Jestliže se časové entity mění v diskrétních krocích, pak bude vyhovovat diskrétní model, tedy celočíselná časová škála. Když změnu časové entity není možné přirozeným způsobem rozdělit do diskrétních kroků, pak bude vhodný spojitý model času, neboli reálná časová škála. Konečnost a ohraničenost času. Čas může být modelován jako konečný (časová škála odpovídá intervalu) nebo nekonečný (časová škála je reprezentována jako přímka), resp. jako ohraničený, kdy existuje poslední časový bod (časová škála jako uzavřený interval) nebo neohraničený, kdy neexistuje poslední časový bod (časová škála jako otevřený interval nebo jako přímka). Tok času. Na základě přirozeného vnímání plynutí času jej můžeme zobrazit jako lineární nebo jako plynutí v kruhu (opakující se časové entity, kupř. cyklus ročních období nebo jízdní řád). Pokud je potřebné vyjádřit neurčitost vztahující se na budoucnost, další možností je rozvětvený tok času. Jednotlivé větve toku času představují možné světy, které mohou nastat vývojem současného světa ([29]). O paralelním toku času mluvíme, kdy je tatáž časová entita vnímána/reprezentována na rozličné časové škále. 2.3 Časová vymezení Součástí reprezentace času a souvisejících pojmů je též určení, jakého typu jsou časové vztahy a jaké jsou přípustné časové výrazy dané reprezentaci (problémy splnění časových omezení). Podle povahy typu časových vztahů můžeme odlišit určení kvantitativní, kvalitativní a fuzzy. Kvantitativní určení. V nejjednodušším případě představuje časovou informaci datum nebo jiná přesná číselná hodnota, a časové vymezení má podobu absolutní numerické hodnoty. Dobu trvání lze vyjádřit a vypočítat jednoduchým způsobem. Obecněji může být k dispozici jen informace o časové vzdálenosti událostí. Časové vymezení má pak podobu dvojice numerických hodnot, které představují dolní a horní hranici, kdy mohla událost v čase nastat. Kvalitativní určení. Allenova algebra ([2]) definuje množinu třinácti vzájemně se vylučujících binárních vztahů, které mohou existovat mezi dvěma časovými intervaly (kupř. shodný-začátek, překrývá-se, shoduje-se). Nad množinou těchto vztahů uvažuje jejich všechny možné disjunkce, které umožňují vyjádřit libovolný vztah mezi dvěma intervaly. Kvalitativní vztah mezi intervaly může být určen i pomocí neúplné informaci o koncových bodech intervalu ([19]). Časová omezení mohou být též určena kombinací kvantitativního a kvalitativního způsobu ([24], [30]). Fuzzy určení. Obecný model pro reprezentaci a zpracování fuzzy časových znalostí ([15]) definuje datum jako rozdělení možnosti na spojité lineární časové škále. Model používá interval jako základní stavební jednotku času a definuje ho jako fuzzy množinu časových bodů mezi dvěma daty. Pro daný problém můžeme zformulovat výrazy, které představují časová omezení kladená na časová vymezení časových entit souvisejících s daným problémem. Dostáváme tak problém splnění časových omezení (temporal constraint satisfaction problem, [8]). Typickou úlohou je kontrola konzistentnosti, vytvoření jednoho nebo více řešení či odvození minimální sítě.

2.4 Reprezentace času a časové uvažování Fenomén času můžeme reprezentovat různými způsoby. Jako první reprezentace času můžeme zmínit situační kalkul McCarthyho a Hayese ([28]) nebo temporální logiku McDermotta ([29]), které používaly jako základní stavební jednotku času okamžik. Allenova intervalová algebra vychází z časového intervalu ([2], [3]). Kromě formalizace fenoménu času a rozšíření jazyka reprezentace o časový aspekt znalostí potřebujeme i nástroje, které umožňují určit pravdivost časových tvrzení zformulovaných v tomto rozšířeném jazyce ([35]). Jelikož je odvozování v umělé inteligenci většinou založeno na logice, časové uvažování představuje zejména zahrnutí času do logiky. Vytváříme tedy vazbu mezi nečasovým tvrzením (atemporálním tvrzením, tzn. neobsahujícím časové vymezení nebo odkaz na čas) a časovým vymezením (temporal reference). Existují tři základní možnosti, které se liší použitou logikou: logika prvního řádu, temporální modální logika a reifikovaná temporální logika. Logika prvního řádu. V logice prvního řádu je čas vyjádřen jako další proměnná. Výraz (koná_se (KUZV05), t) tak bude znamenat, že událost KUZV05 se koná v časové stavební jednotce t (t je časový okamžik). Časové vymezení je vyjádřeno absolutně, t.j. jako číselná hodnota reálná (spojitá povaha času) nebo celočíselná (diskrétní povaha času). Pro uvažování o fyzikálních procesech je tento způsob časového uvažování obvykle dostačující, nevyhovuje ale kupř. pro uvažování o činech a v porozumění přirozenému jazyku. Je totiž obtížné vyjádřit časová vymezení jako teď, pak, od, dokud, zatímco a podobně pouze pomocí číselné hodnoty. Výhodou časového uvažovaní založeného na logice prvního řádu je poměrně malá výpočetní náročnost a propracovaný důkazový aparát. Nevýhodou je malá vyjadřovací síla. Temporální modální logika. Temporální modální logika vychází z modální logiky, od které se liší tím, že místo jedné množiny operátorů používá dvě. Jedna množina operátorů se používá pro časová vymezení vztahující se na minulost (Pp pro „výrok p byl pravdivý“, Hp pro „výrok p byl vždy pravdivý“), druhá pro časová vymezení vztahující se na budoucnost (Fp pro „výrok p bude pravdivý“, Gp pro „výrok p bude vždy pravdivý“). Temporální modální logika nespecifikuje, kterou základní stavební jednotku používá (okamžik nebo interval). Časové vymezení je vyjádřeno relativně, protože tvrzení jsou uvedeny do časové souvislosti se současnými událostmi nebo událostmi budoucími či minulými. Temporální modální logika se často používá v oblasti porozumění přirozenému jazyku, kde je výhodou efektivita zápisu. V porovnání s logikou prvního řádu je vyjadřovací síla temporální modální logiky větší, ale dokazování tvrzení je obtížnější . Reifikovaná temporální logika. Reifikovaná temporální logika vychází z logiky prvního řádu, kterou reifikuje. Reifikace logiky znamená použití metajazyka, v kterém se tvrzení zformulované v logice prvního řádu (nebo v modální či jiné logice) stává prepozičním termem v predikátu metajazyka. V metajazyce pak odvozujeme pravdivostní hodnotu predikátu, a z ní pak usuzujeme na pravdivost tvrzení použitých jako prepoziční termy. V případě reifikované temporální logiky používá predikát metajazyka (kupř. predikát true) nečasovou (atemporální) formuli logiky prvního řádu a výraz časového vymezení jako argumenty. Predikátem true (nečasový výraz, časové vymezení) tak vyjádříme, že uvedený nečasový výraz je pravdivý vzhledem k uvedenému časovému vymezení. Uvedeným predikátem true můžeme vyjádřit nejen časové vymezení platnosti uvedeného nečasového výrazu, ale též schéma (vzorec) časového výskytu. Výhodou reifikované temporální logiky je vyšší vyjadřovací síla v reprezentaci časových znalostí na obecnější úrovni, nevýhodou její složitost.

3 Granularita času Svět vnímáme na různých škálách a abstrahujeme z něj pouze ty objekty, které v daném okamžiku potřebujeme. Schopnost konceptualizovat svět na různých úrovních granularity a přepínat mezi nimi podle potřeby je základní podmínkou naší inteligence a flexibility ([21]). Vhodnou škálu (granularitu) volíme nejen u prostorového vymezení objektů (kupř. [37]), ale i u časového vymezení (časová granularita). 3.1 Definice granularity času V literatuře se vyskytují různé varianty definice granularity času ([8], [12], [11]), my uvádíme klasickou definici autorů Bettini, Wang a Jajodia ([4]). Granularita času je zde definována jako časový typ. Definice Ať (I, ≤I) (index) je diskrétní lineární uspořádání izomorfní s podmnožinou celých čísel s obvyklou relací uspořádání, a ať (A, ≤A) (absolutní čas) je lineární uspořádání. Pak časový typ nad (I, A) je takové zobrazení µ z I do 2A, že platí: 1. jestliže µ(i)≠ø a µ(j)≠ø, kde i 31, březen_2005 (i) = ø). Z definice granularity též plyne, že granule nemusí být spojitým intervalem absolutního času. Příkladem je granularita pracovní_měsíc, kde pracovní_měsíc (i) je

sjednocení několika nesouvisejících intervalů absolutního času (vymezených jednotlivými pracovními dny daného měsíce a s vynecháním dnů pracovního klidu a svátků). Je též možné definovat takové granularity, které zobrazují na stejný soubor podmnožin absolutního času, ale jednotlivé podmnožiny jsou obrazem jiných hodnot z množiny indexů. Příkladem je granularita den kalendáře křesťanského a kalendáře židovského. 3.2 Vlastnosti granularity Můžeme definovat následující vlastnosti granularity ([COMO4]). Navenek spojitá. Granularita je navenek spojitá, jestliže jednotlivé neprázdné granule na sebe navazují, čili mezi jednotlivými neprázdnými granulemi neexistují neprázdné intervaly absolutního času. Příkladem je granularita den. Protipříkladem je granularita pracovní_den, protože mezi (pracovním) pátkem a (pracovním) pondělím je neprázdný interval absolutního času vymezen dny sobota a neděle Uvnitř spojitá. Granularita je uvnitř spojitá, jestliže jednotlivé granule neobsahují mezery. Příkladem je granularita měsíc. Protipříkladem je pracovní_měsíc, protože pozůstává z nesouvisejících intervalů absolutního času. Spojitá. Granularita je spojitá, jestliže je zároveň navenek spojitá a uvnitř spojitá. Úplná. Granularita je úplná, jestliže granule úhrnně pokrývají celou množinu absolutního času. Příkladem jsou běžné kalendářní granularity. Protipříkladem je granularita léta_po_pádu_železné_opony. Jednotná. Granularita je jednotná, jestliže je kardinalita všech neprázdných granulí stejná. Příkladem je granularita den, protipříkladem je granularita měsíc. 3.3 Varianty granularity Definice granularity uvedená v části 3.1 je obecná, a můžeme ji více specifikovat dalšími podmínkami ([4]). Dostaneme tak různé varianty granularity. Množina indexů I. Jako množinu indexů I můžeme zvolit množinu přirozených čísel, množinu celých čísel nebo jejich libovolnou konečnou podmnožinu. Množina absolutního času A. Množinu absolutního času A volíme podle toho, jestli pracujeme s diskrétní nebo spojitou strukturou času. Pokud v problémové oblasti existuje předem určená, neměnná základní granularita (kupř. vteřina), a nebudeme potřebovat časová vymezení kratší než tato základní granularita, pak vyhovuje diskrétní struktura času. Jestliže naopak potřebujeme vymezit libovolně jemnou granularitu, pak je vhodná spojitá struktura času. Na množinu absolutního času můžeme klást i další podmínky, kupř. ohraničenost zleva a/nebo zprava. Struktura granulí. Strukturu granulí můžeme omezit různými způsoby podle toho, jaké vlastnosti granularity definované výše zakazujeme resp. vyžadujeme. Jestliže budeme požadovat, aby granularita byla kupř. spojitá, úplná a jednotná, pak granularita den těmto požadavkům vyhovuje, ale granularita měsíc a rok ne (obě nejsou jednotné). Některé konkrétní varianty granularity jsou zkoumány podrobněji ([9], [14]). Práce ([14]) se zabývá takovou variantou granularity, kde množina indexů I je celočíselná, množina absolutního času A je reálná, a je přípustná jen spojitá a úplná granularita. Tato varianta modularity je vhodná pro velké temporální databáze.

3.4 Systémy granularit a jejich vlastnosti V mnohých problémových oblastech je potřebné pracovat s takovým modelem, který umožňuje reprezentaci časových vymezení v různých granularitách a zaručuje správnou interpretaci tvrzení s časovým vymezením včetně přechodu z jedné granularity do jiné. Jako příklad můžeme uvést temporální databáze ([5], [10], [16]), porozumění přirozenému jazyku ([20]), dolování v datech ([1], [6], [27], [25]) a řešení problémů ([36], [32]). V systémech s více granularitami pak můžeme zkoumat, jaké vztahy existují mezi granularitami. Mezi dvěma granularitami můžeme definovat následující vztahy ([34]). Jemnější (G1, G2). Granularita G1 je jemnější než granularita G2, jestliže každá granule granularity G1 je podmnožinou nějaké granule granularity G2. Formálně, ∀i ∃j G1 (i) ⊆ G2 (j). Vztah jemnější existuje například mezi granularitami den a měsíc, ale neexistuje mezi granularitami týden a rok (část týdne může spadat do jednoho roku, zbytek do roku následujícího). Podgranularita (G1, G2). Granularita G1 je podgranularitou granularity G2, jestliže každá granule granularity G1 je rovna nějaké granuli granularity G2. Formálně, ∀i ∃j G1 (i) = G2 (j). Vztah podgranularita existuje například mezi granularitami přestupný_rok a rok. Menší (G1, G2). Granularita G1 je menší než granularita G2, jestliže každá granule granularity G1 je podmnožinou granule s příslušným indexem granularity G2. Formálně, ∀i G1 (i) ⊆ G2 (i). Vztah menší existuje například mezi granularitami pracovní_týden a týden. Sdruženo (G1, G2). Granularita G1 je sdružena do granularity G2, jestliže každá granule granularity G2 je výsledkem sjednocení libovolného počtu za sebou následujících granulí granularity G1. Formálně, ∀i ∃S = {j, j+1, ..., j+k} (j, k ≥ 0), že G2 (i ) = ∪ m∈S G1 (m) . Vztah sdruženo existuje například mezi granularitami den a měsíc. Posunuto (G1, G2). Granularita G1 je posunuta vzhledem ke granularitě G2, jestliže granule granularity G2 dostaneme posunutím indexu granulí granularity G1 o stejnou hodnotu (větší nebo rovnou 0). Formálně, ∃p ≥ 0 ∀i G1 (i) = G2 (i + p). Vztah posunuto existuje kupříkladu mezi granularitami rok a rok_počínaje_rokem_sametové_ revoluce. 3.5 Konverze dat Jestliže model problémové oblasti umožňuje formulovat časová vymezení v různých granularitách, může být potřebné konvertovat časové vymezení použitím jedné granularity na časové vymezení použitím jiné granularity ([4]). Kupř. k dané granuli x granularity X hledáme granuli y = Y(j) granularity Y tak, aby granule y (t.j. odpovídající interval absolutního času) zcela pokrývala granuli x = X(i) (t.j. odpovídající interval Y absolutního času). Formálně, zajímá nás hodnota výrazu i  X = j . Jestliže taková granule y=Y(j) existuje, pak monotónnost granularity zaručuje jednoznačné určení granule y. Existence granule y ovšem obecně není zaručená. Jestliže pro všechny granule y granularity Y platí, že granule x=X(i) není podmnožinou granule y, pak Y rok hodnota výrazu i  X není definována. Kupříkladu hodnota výrazu i týden nemusí být rok

definována pro některé granule týden(i), a hodnota výrazu i svátek existuje pro všechny

granule svátek(i). Jestliže pro granularity X a Y platí, že X je jemnější než Y, pak Y hodnota výrazu i  X existuje pro všechny granule X(i). Konverzi časového vymezení lze provést i opačným směrem, kdy k dané granuli x granularity X hledáme k za sebou následujících granulí granularity Y takových, že úhrnně pokryjí granuli x = X(i). Formálně, hledáme takové indexy j a k, pro které X X(i) = Y(j + 0) ∪ ... ∪ Y(j + k - 1) (píšeme i Y = ( j , k ) ). Kupříkladu k dané granuli březen granularity měsíc hledáme všechny granule granularity den, které úhrnně tuto granuli vymezují, t.j. březen01 až březen31. Jestliže pro granularity X a Y platí, že X granularita Y je sdružena do granularity X, pak hodnota výrazu i Y je vždy definována. 3.6 Reprezentace časové granularity Časovou granularitu můžeme reprezentovat v různých reprezentačních schématech, které se liší vyjadřovací sílou, efektivitou a hutností zápisu ([11]). Existující reprezentační schémata můžeme rozdělit na algebraické, logické a páskové (automatové). Algebraická reprezentace. Nové granularity jsou odvozeny z existujících použitím konečné množiny kalendářových operátorů, přičemž se předpokládá existence základní granularity. Granularita je tedy definována jako algebraický výraz. Existují algoritmy pro konverzi granulí z jedné granularity do jiné, a pro sémantickou konverzi tvrzení souvisejících s různými granularitami. Formalizmus sbírka časových intervalů ([17]) se zakládá na strukturovaných množinách časových intervalů. Řád strukturované množiny intervalů představuje hloubku struktury: sbírka prvního řádu je uspořádaný seznam časových intervalů, sbírka n-tého řádu je uspořádaný seznam sbírek (n-1)-ho řádu. Každý interval představuje množinu navazujících momentů. Pro manipulaci se sbírkami časových intervalů se používají operátory dělení intervalu na kratší intervaly a výběr intervalu. Podobný formalizmus algebraické reprezentace granularity představuje n formalizmus řezu ([33]). Řez je definován jako ∑i =1 Oi ∗ Ci > D , kde sčítance součtu představují začátky intervalů, Ci kalendář (t.j. periodickou nekonečnou množinu za sebou následujících intervalů), Oi množinu přirozených čísel nebo klíčové slovo all, a D trvání intervalů. Kupříkladu zápis all.rok + all.měsíc + {1}.den > 7.den vymezuje prvních sedm dnů každého měsíce každého roku. Formalizmus sbírky intervalů a formalizmus řezu umožňují definovat konečné granularity bez mezer a nekonečné periodické granularity bez mezer ([7]). Třetí formalizmus algebraické reprezentace granularity o kterém se zmíníme, je kalendářová algebra ([34]). Kalendářová algebra používá parametrické kalendářové operace. Seskupovací operace seskupují vybrané granule dané granularity s cílem vytvořit granule nové granularity. Granulové operace zachovávají granule dané granularity, ale vybírají z nich ty granule, které budou představovat novou granularitu. V kalendářové algebře lze reprezentovat všechny konečné a nekonečné periodické granularity. Logická reprezentace. V logické reprezentaci granularity jsou granularity a jejich vazby reprezentovány pomocí matematických struktur, tzv. vrstvených struktur ([31], [18]). Vrstvená struktura pozůstává z (případně) nekonečné množiny provázaných časových domén o různé granularitě. Tato struktura definuje relevantní časové domény a vztahy mezi časovými body z různých časových domén. Jsou definované operátory přemístění, které umožňují horizontální pohyb v rámci dané časové domény a operátory

projekce, které umožňují vertikální pohyb napříč časovými doménami. Použitím operátorů přemístění a projekce je možné zahrnout do jediné logické formule různé časové granularity. Použitím temporálních logických formulí lze vyjádřit vlastnosti časových granularit. Logická reprezentace ([11]) umožňuje modelovat pomocí temporálních logických formulí jak časové granularity, tak jejich vlastnosti. Pásková a automatová reprezentace. V páskové reprezentaci granularity je nekonečná granularita definována jako nekonečná páska nad vhodnou konečnou abecedou ([39]). Obdobná je reprezentace automatem s jednou páskou ([12]), kde automat je variantou Büchi automatu, který akceptuje jedinou nekonečnou pásku. Výrazy zformulované v kalendářové algebře lze převést na ekvivalentní automat s jedinou páskou ([13]).

4 Další související otázky V souvislosti s reprezentací času je určitě vhodné zmínit časové dolování v datech, které se zabývá objevováním časových vzorců událostí, přičemž časové vymezení dat může být vztaženo i k různým granularitám ([25]). Reprezentace časových závislostí mezi událostmi a jejich důsledky je součástí reprezentace příčinných závislostí mezi událostmi a jejich důsledky. Formalizmus ([26]) umožňuje nejen reprezentaci okamžitých a opožděných důsledků, ale i formulací z běžného života typu „důsledky nemohou předcházet příčině“. Z hlediska sémantického webu, sdílení a znovupoužití znalostí mohou být zajímavé ontologie času (kupř. [22], [23], [40]).

5 Závěr Cílem tohoto článku bylo uvést čtenáře do problematiky času, časového uvažování a obzvláště pak časové granularity. V seznam literatury najde čtenář s hlubším zájmem o tuto problematiku odkazy na další zdroje.

Literatura [1] Agrawal, R., Srikant, R.: Mining sequential patterns. In Yu, P.S., Chen, A.L.P. (eds.): Proc. of the International Conference on Data Engineering, IEEE Press (1995) 3-14. [2] Allen, J.F.: Maintaining knowledge about temporal intervals. Communication of the ACM 26 (11) (1983) 832-834. [3] Allen, J.F.: Towards a general theory of action and time. Artificial Intelligence 32 (1984) 123-154. [4] Bettini, C., Wang, X.S., Jajodia, S.: A general framework for time granularity and its application to temporal reasoning. Technical Report ISSE-TR-96-10 (1996). [5] Bettini, C., Brodsky, A., Jajodia, S., Wang, X.S.: Logical design for temporal databases with multiple granularities. ACM Transactions on Database Systems 22 (1997) 115-170. [6] Bettini, C., Jajodia, S., Lin, J., Wang, X.S.: Discovering frequent event patterns with multiple granularities in time sequences. IEEE Transactions on Knowledge and Data Enginnering 10 (1998) 222-237.

[7] Bettini, C., Sibi, R.D.: Symbolic representation of user-defined granularities. Annals of Mathematics and Artificial Intelligence 30 (2000) 53-92. [8] Bettini, C., Wang, X.S., Jajodia, S.: Solving multi-granularity temporal constraint networks. Artificial Intelligence 140 (2002) 107-152. [9] Ciapessoni, E., Corsetti, E., Montanari, A., San Pietro, P.: Embeddign time granularity in a logical specification language for synchronous real-time systems. Science of Computer Programming 20 (1993) 141-171. [10] Combi, C., Pozzi, G.: A Temporal Data Model Managing Intervals with Different Granularities and Indeterminacy from Natural Language Sentences. The VLDB Journal 9 (2001) 294-311. [11] Combi, C., Franceschet, M., Peron, A.: Representing and reasoning about temporal granularities. Journal of Logic Computation 14 (1) (2004) 51-77. [12] Dal Lago, U., Montanari, A., Puppis, G.: Towards Compact and Tractable Automaton-Based Representations of Time Granularities. In Blundo, C., Laneve, C. (eds.): ICTCS 2003, Lecture Notes in Computer Science 2841 (2003) 72-85. [13] Dal Lago, U., Montanari, A., Puppis, G.: Time granularities, calendar algebra, and automata. Technical Report 4/2003, Department of Mathematics and Computer Science, University of Udine (2003). [14] Dean, T: Artificial intelligence: using temporal hierarchies to efficiently maintaining large temporal databases. JACM 36 (1989) 687-718. [15] Dubois, D., Prade, H.: Processing fuzzy temporal knowledge. IEEE Transactions on System, Man and Cybernetics 14 (4) (1989) 729-744. [16] Dyreson, C.E., Snodgrass, R.T.: Temporal granularity. In Snodgrass, R.T. (ed.): The TSQL2 Temporal Query Language, Kluwer Academic Press (1995) 347-385. [17] Foster, D., Leban, B., McDonald, D.: A representation for collections of temporal intervals. In Proc. of the ANCAI (1986) 367-371. [18] Franceschet, M.: Dividing and conquering the layered land. PhD thesis, Department of Mathematics and Computer Science, University of Udine (2001). [19] Freksa, C.: Temporal reasoning based on semi-intervals. Artificial Intelligence 54 (1992) 199-227 [20] Fum, D., Guida G., Montanari, A., Tasso, C.: Using levels and viewpoints in text representation. In Proc. of the International Conference on Artificial Intelligence and Information-Control Systems of Robots (1989) 37-44. [21] Hobbs, J.R.: Granularity. (2002). [22] Hobbs, J.R.: A DAML Ontology of Time. (2002). [23] Hobbs, J.R., Pan, F.: An Ontology for the Semantic Web. ACM Transactions on Asian Language Information Processing 3 (1) (2004) 66-85. [24] Kautz, H.A., Ladkin, P.B.: Integrating metric and qualitative temporal reasoning. In Proc AAAI-91 (1991) 241-246. [25] Li, Y., Wang, X.S., Jajodia, S.: Discovering Temporal Patterns in Multiple Granularities. In Roddick, J.F., Hornsby, K. (eds.): TSDM 2000, Lecture Notes in Artificial Intelligence 2007 (2001) 5-19. [26] Ma, J., Knight, B., Peng, T: Representing Temporal Relationships Between Events and Their Effects. In Proc. of the 4th International Workshop on Temporal Representation and Reasoning (1995) 148-152. [27] Mannila, H., Toivonen, H., Verkamo, I.: Discovering frequent episodes in sequences. In Fayyad, U.M., Uthurusamy, R. (eds.): Proc. of the International Conference on Knowledge Discovery and Data Mining, AAAI Press (1995).

[28] McCarthy, J.M., Hayes, P.: Some philosophical problems from the standpoint of AI. Machine Intelligence 4 (1969) 463-502. [29] McDermott, D.: A temporal logic for reasoning about process and plans. Cognitive Science 6 (1982) 101-155 [30] Meiri, I.: Combining qualitative and quantitative constraints in temporal reasoning. In Proc AAAI-91 (1991). [31] Montanari, A.: Metric and Layered Temporal Logic for Time Granularity. ILLC Dissertation Series 1996-02, Institute for Logic, Language and Computation, University of Amsterdam (1996). [32] Mota, E., Robertson, D.: Representing interaction of agents at different time granularities. In Proc. of the International Workshop on Temporal Representation and Reasoning, IEEE Computer Society Press (1996) 72-79. [33] Niezette, M., Stevenne, J.: An efficient symbolic representation of periodic time. In Proc. of the International Conference on Information and Knowledge Management, Lecture Notes in Computer Science 752 (1993) 161-168. [34] Ning, P., Jajodia, S., Wang, X.S.: An algebraic representation of calendars. Annals of Mathematics and Artificial Intelligence 36 (2002) 5-38. [35] Pani, A.K., Bhattacharjee, G.P.: Temporal Representation and Reasoning in Artificial Intelligence: A Review. Mathematical and Computer Modelling 34 (2001) 55-80. [36] Poesio, M., Brachman, R.J.: Metric constraints for maintaining appointments: Dates and repeated activities. In Proc. of the National Conference on Artificial Intelligence, MIT Press (1991) 253-259. [37] Reitsma, F., Bittner, T.: Scale in Object and Process Ontologies. In Kuhn, W., Worboys, M.F., Timpf, S. (Eds.): COSIT 2003, Lecture Notes in Computer Science 2825 (2003) 13-27. [38] Vilain, M.B.: A system for reasoning about time. In Proc. AAAI-82, Pittsburg, PA (1982) 197-201. [39] Wijsen, J.: A string-based model for infinite granularities. In Proc. of the AAAI Workshop on Spatial and Temporal Granularity, AAAI Press (2000) 9-16. [40] Zhou, Q., Fikes, R.: A Reusable Time Ontology. Knowledge Systems Laboratory, Technical report (2000).