Theory is Forever. Essays Dedicated to Arto Salomaa on the Occasion of his 70th Birthday

0103329 - UIVT-O 20040070 RIV DE eng M - Monography Chapter
Verbaan, P. - van Leeuwen, J. - Wiedermann, Jiří
Complexity of Evolving Interactive Systems.
[Složitost evolučních interaktivních systémů.]
Theory is Forever. Essays Dedicated to Arto Salomaa on the Occasion of his 70th Birthday. Berlin: Springer, 2004 - (Karhumäki, J.; Maurer, H.; Paun, G.; Rozenberg, G.), s. 268-281. Lecture Notes in Computer Science, 3113. ISBN 3-540-22393-2
R&D Projects: GA ČR GA201/02/1456
Institutional research plan: CEZ:AV0Z1030915
Keywords : evolving interactive computing * lineages of automata
Subject RIV: BA - General Mathematics

We study a versatile model of evolving interactive computing: lineages of automata. A lineage consists of a sequence of interactive finite automata, with a mechanism of passing information from each automaton to its immediate successor. Lineages enable a definition of a suitable complexity measure for evolving systems. We show several complexity results, including a hierarchy result.

Zkoumá se všestranný model evolučních interaktivních výpočtů, tzv. linie automatů. Linie se skládá z interaktivních konečných automatů opatřených mechanizmem předávání informací z automatu na jeho následníka. Linie umožňují definici vhodných měr složitosti pro evoluční systémy. Dokážeme několik složitostních výsledků včetně výsledků o hierarchii.
Permanent Link: http://hdl.handle.net/11104/0010640