Functional Tuple Pairs and Applications to Higher-Order Complexity Theory Nesta palestra, discutimos os primeiros desenvolvimentos de pares de tuplas funcionais, ou seja, um método de interpretação para reescrita de ordem superior e programação funcional.Deivid Vale - Radboud University Nijmegen em 24/09/2021 Abstract In this talk we discuss early developments of functional tuple pairs, i.e., an interpretation method for higher-order rewriting and functional programming. The main goal of this technique is thought to be twofold: first, we show how tuple interpretation subsumes earlier interpretation techniques and might be used in combination of classic methods like dependency pairs and rule removal; this is already the case in first-order rewriting. Second, we use tuple interpretations as a way to express runtime complexity for higher-order algebraic systems discussing a proper higher-order notion of program-data. We show that under mild assumptions we can derive complexity bounds for closed higher- order programs. We also show preliminary results on those interpretations being used as a main technique in implicit complexity theory as we might be able to capture higher-order functional complexity classes, for instance, the class of Basic Feasible Functionals (BFFs). Local e Data Tema: Functional Tuple Pairs and Applications to Higher-Order Complexity TheoryPalestrante: Deivid Vale - Radboud University NijmegenData: 24/09/2021 Secretaria Fale ConoscoRoteiros e ProcedimentosSolicitaçõesTelefones e e-mail Seminários Álgebra Análise Geometria Mecânica Sistemas Dinâmicos Teoria da Computação Teoria da Probabilidade Teoria dos Números
