Normed semialgebras: a mathematical model for the complexity analysis of programs and algorithms

摘要

Motivated by the recent applications of complexity of tree automata to obtaining optimal deterministic exponential time algorithms in some important modal logic of programs, we construct a wide class of complexity spaces which are modelled as normed semialgebras. Thus we obtain, in the dual context, a suitable setting to carry out a description of the complexity functions that are generated by exponential time algorithms. An approach to this topic, based on the use of supremum norm on unitary semialgebras has recently been discussed by the first three-listed authors.