4 papers
Length Generalization Bounds for Transformers
Andy Yang, Pascal BergsträÃer, Georg Zetzsche +2
Length generalization is a key property of a learning algorithm that enables it to make correct predictions on inputs of any length, given finite training data. To provide such a g…
General Decidability Results for Systems with Continuous Counters
A. R. Balasubramanian, Matthew Hague, Rupak Majumdar +2
Counters that hold natural numbers are ubiquitous in modeling and verifying software systems; for example, they model dynamic creation and use of resources in concurrent programs.…
Softmax Transformers are Turing-Complete
Hongjian Jiang, Michael Hahn, Georg Zetzsche +1
Hard attention Chain-of-Thought (CoT) transformers are known to be Turing-complete. However, it is an open problem whether softmax attention Chain-of-Thought (CoT) transformers are…
Presburger Functional Synthesis: Complexity and Tractable Normal Forms
S. Akshay, A. R. Balasubramanian, Supratik Chakraborty +1
Given a relational specification between inputs and outputs as a logic formula, the problem of functional synthesis is to automatically synthesize a function from inputs to outputs…