Second-Order Simple Grammars

Colin Stirling

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Higher-order notations for trees have a venerable history from the 1970s and 1980s when schemes (that is, functional programs without interpretations) and their relationship to formal language theory were first studied. Included are higher-order recursion schemes and pushdown automata. Automata and language theory study finitely presented mechanisms for generating languages. Instead of language generators, one can view them as process calculi, propagators of possibly infinite labelled transition systems. Recently, model-checking techniques have been successfully extended to these higher-order notations in the deterministic case
Original languageEnglish
Title of host publicationCONCUR 2006 - Concurrency Theory
Subtitle of host publication17th International Conference, CONCUR 2006, Bonn, Germany, August 27-30, 2006, Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages15
ISBN (Electronic)978-3-540-37377-3
ISBN (Print)978-3-540-37376-6
Publication statusPublished - 2006


Dive into the research topics of 'Second-Order Simple Grammars'. Together they form a unique fingerprint.

Cite this