The supremum asymmetric norm on sequence algebras

作     者：L.M. García-Raffi S. Romaguera E.A. Sánchez-Pérez 

作者机构：Escuela de Caminos Departamento de Matemática Aplicada Universidad Politécnica de Valencia 46071 Valencia Spain 

出 版 物：《Electronic Notes in Theoretical Computer Science》 

年 卷 期：2003年第74卷

页      面：39-50页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：asymmetric norms semialgebra biBanach exponential time algorithm sup P(n) -complexity space isometrically isomorphic 

摘      要：Recently, E.A. Emerson and C.S. Jutla (SIAM J. Comput., 1999), have successfully applied complexity of tree automata to obtain optimal deterministic exponential time algorithms for some important modal logics of programs. The running time of these algorithms corresponds, of course, to complexity functions which are potential functions and, thus, they do not belong, in general, to any dual p -complexity space. Motivated by these facts we here introduce and study a very general class of complexity spaces, which provides, in the dual context, a suitable framework to carry out a description of the complexity functions that generate exponential time algorithms. In particular, such spaces can be modelled as biBanach semialgebras which are isometrically isomorphic to the positive cone of the asymmetric normed linear space consisting of bounded sequences of real numbers endowed with the supremum asymmetric norm.