Simply typed fixpoint calculus and collapsible pushdown automata

DOI10.1017/S0960129514000590MaRDI QIDQ2973243zbMATH OpenOpenAlexFDO

Authors S. Salvati, Igor Walukiewicz

Publication date 3 April 2017

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0960129514000590

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Functional programming and lambda calculus (68N18)

Recommendations

• Recursive schemes, Krivine machines, and collapsible pushdown automata
• On the \(\lambda Y\) calculus
• A Finite Semantics of Simply-Typed Lambda Terms for Infinite Runs of Automata
• Unfixing the fixpoint: the theories of the \(\lambda Y\)-calculus
• Recognizability in the Simply Typed Lambda-Calculus

Cites work

• A Saturation Method for Collapsible Pushdown Systems
• A call-by-name lambda-calculus machine
• A practical linear time algorithm for trivial automata model checking of higher-order recursion schemes
• An automata-theoretical characterization of the OI-hierarchy
• Applications of infinitary lambda calculus
• Indexed Grammars—An Extension of Context-Free Grammars
• Krivine machines and higher-order schemes
• LCF considered as a programming language
• On full abstraction for PCF: I, II and III
• Recursive schemes, Krivine machines, and collapsible pushdown automata
• The IO- and OI-hierarchies
• Using models to model-check recursive schemes

Cited in

(9)

• Homogeneity without loss of generality
• Recursion schemes and the WMSO+U logic
• scientific article; zbMATH DE number 7199579 (Why is no real title available?)
• The Complexity of the Diagonal Problem for Recursion Schemes
• Unfixing the fixpoint: the theories of the \(\lambda Y\)-calculus
• On the \(\lambda Y\) calculus
• Cost Automata, Safe Schemes, and Downward Closures
• Simply typed convertibility is \textsc{Tower}-complete even for safe lambda-terms
• Types from Frames as Finite Automata

This page was built for publication: Simply typed fixpoint calculus and collapsible pushdown automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2973243)