Tyrolean Complexity Tool
A Complexity Analyser for Term Rewrite Systems
TcT is a tool for automatically proving polynomial upper bounds on the derivational complexity and runtime complexity of term rewriting systems. It is developed by members of the Computation with Bounded Resources research group.

TcT features a majority of the known techniques for the automatic characterisation of polynomial complexity of a TRS, see also the list of supported techniques. It is currently the only complexity tool implementing dedicated techniques for all complexity categories of that competition. The predecessor of TcT is still available from here.


TcT won a Kurt Gödel medal

In 2014, the first "FLoC Olympic Games" have been conducted during the Vienna Summer of Logic. During the games, several automatic tools competed in 14 different competitions about complexity, determinacy, satisfiablity, termination, etc. TcT competed in the termination competition and won the prize for the most powerful tool in complexity analysis of term rewrite systems.
TcT version 2.0.1 released

TcT version 2.0.1 has been released. This minor release comes with updated documentation, minor bugfixes, and a more consistent naming of techniques in Tct.Instances.
TcT version 2.0 released

TcT version 2.0 has been released. Besides bug-fixes and a wealth of minor improvements, notably this release adds to version 1.9:
Web Interface Updated

Our web interface has been polished, it features new examples, the competition strategy of 2012 and a dedicated strategy for our RaML collection.
Complexity Competition 2012

TcT participated in all four complexity categories of the complexity competition 2012. TcT won the runtime complexity category. It is the only tool participating in the innermost derivational complexity category, and the only open source tool capable of proving innermost runtime complexity. TcT could signifficantly increase its power for innermost runtime complexity, and was placed closely after AProVE (closed source).
Web Interface

TcT now features an easy to use web interface.
Resource aware ML

We have translated the Resource aware ML testbed to term rewrite systems. The resulting set of TRSs can be downloaded from here.
TcT version 1.9 released

This version presents the last milestone before version 2.0. Besides various bugfixes, most notably following new features are added:
News archive


TcT is currently under development by Martin Avanzini, Andreas Kochesser, Georg Moser, Michael Schaper and Maria Schett.