ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Twenty-Second Annual IEEE Symposium on

Logic in Computer Science (LICS 2007)

Invited Paper: Higher-Order Matching, Games and Automata (at LICS 2007)

Authors: Colin Stirling


Higher-order matching is the problem given t = u where t, u are terms of simply typed \lambda-calculus and u is closed, is there a substitution \theta such that t\theta and u have the same normal form with respect to \beta \eta-equality: can t be pattern matched to u? This paper considers the question: can we characterize the set of all solution terms to a matching problem? We provide an automata-theoretic account that is relative to resource: given a matching problem and a finite set of variables and constants, the (possibly infinite) set of terms that are built from those components and that solve the problem is regular. The characterization uses standard bottom-up tree automata.


    author = 	 {Colin Stirling},
    title = 	 {Higher-Order Matching, Games and Automata},
    booktitle =  {Proceedings of the Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS 2007)},
    year =	 {2007},
    month =	 {July}, 
    pages =      {326--335},
    location =   {Wroclaw, Poland}, 
    note =       {Invited Talk},
    publisher =	 {IEEE Computer Society Press}

Last modified: 2022-10-3113:49
Sam Staton