# CLRKDNet: Speeding up Lane Detection with Knowledge Distillation

Weiqing Qi, Guoyang Zhao, Fulong Ma, Linwei Zheng and Ming Liu This work was
supported by Guangzhou-HKUST(GZ) Joint Funding Program (No. 2024A03J0618),
awarded to Prof. Ming Liu. (Corresponding author: Ming Liu
(email:eelium@hkust-gz.edu.cn).)Weiqing Qi, Guoyang Zhao, Fulong Ma, Linwei
Zheng and Ming Liu are with the Hong Kong University of Science and Technology
(Guangzhou), Nansha, Guangzhou, 511400, Guangdong, China. (email:{wqiad,
gzhao492, fmaaf, lzhengad}@connect.hkust-gz.edu.cn).

###### Abstract

Road lanes are integral components of the visual perception systems in
intelligent vehicles, playing a pivotal role in safe navigation. In lane
detection tasks, balancing accuracy with real-time performance is essential,
yet existing methods often sacrifice one for the other. To address this trade-
off, we introduce CLRKDNet, a streamlined model that balances detection
accuracy with real-time performance. The state-of-the-art model CLRNet has
demonstrated exceptional performance across various datasets, yet its
computational overhead is substantial due to its Feature Pyramid Network (FPN)
and muti-layer detection head architecture. Our method simplifies both the FPN
structure and detection heads, redesigning them to incorporate a novel
teacher-student distillation process alongside a newly introduced series of
distillation losses. This combination reduces inference time by up to 60%
while maintaining detection accuracy comparable to CLRNet. This strategic
balance of accuracy and speed makes CLRKDNet a viable solution for real-time
lane detection tasks in autonomous driving applications. Code and models are
available at: https://github.com/weiqingq/CLRKDNet.

##  I Introduction

Lane detection [28, 14] is a critical aspect of intelligent transportation,
including autonomous driving and Advanced Driver Assistance Systems (ADAS).
Lanes are integral elements of road traffic, delineating vehicular paths and
promoting safer and smoother driving conditions. Detection methods generally
fall into two categories: model-based and feature-based. Model-based
approaches utilize predefined lane models, interpreting lane recognition as a
parameter estimation problem, which helps reduce sensitivity to noise and
limits reliance on extensive local image areas. In contrast, feature-based
approaches classify individual image points as lane or non-lane, relying on
specific characteristics such as edge gradient, width, intensity, and color.
This strategy, however, requires distinct lane edges and strong color
contrasts for accurate detection. Both approaches follow a similar sequence of
steps: region of interest (ROI) extraction, image preprocessing, feature
extraction, and lane fitting.

With the advent of deep learning [7, 13], traditional lane detection methods
have largely been supplanted by more advanced, end-to-end deep learning
approaches. These modern methods eliminate the need for manual feature
engineering and enhance both the robustness and efficacy of detection systems.
Contemporary lane detection techniques can be broadly classified into four
categories: segmentation-based, parametric curve-based, keypoint-based, and
anchor-based methods. Segmentation-based approaches [15, 30, 24] treat lane
detection as a semantic segmentation task, while parametric curve-based
methods [1, 21, 10] model lanes using curve parameters, detecting them through
parameter regression. Keypoint-based methods [18] approach lane detection as a
problem of keypoint estimation followed by integration. Finally, anchor-based
methods [20, 29, 16, 17, 9, 25] employ line-shaped anchors, regressing offsets
of sampled points from these predefined anchors.

Figure 1: FPS vs. F1-score of state-of-the-art methods on CULane benchmarks.

Despite considerable advances in lane detection using deep learning
techniques, there are still opportunities for further enhancements. Lane lines
typically extend over long pixel stretches in images and exhibit
distinguishable characteristics from the road surface at local scales,
underscoring the need to extract both global and local features for accurate
detection. In the paper by Zheng et al. [29], the Cross-Layer Refinement
Network (CLRNet) was introduced, leveraging both high-level semantic and low-
level detailed features. It begins with rough localization using high-level
features, followed by refinement with detailed features for precise lane
positioning. The ROIGather module further captures extensive global contextual
information by linking ROI lane features to the entire feature map,
significantly elevating detection performance compared to previous
methodologies. However, CLRNet’s complexity, including its Feature Pyramid
Network (FPN) and multiple detection heads, increases inference time,
hindering real-time performance crucial for autonomous vehicles. In response,
we developed CLRKDNet, a model designed to reduce inference time while
maintaining accuracy. CLRKDNet simplifies the FPN architecture, opting for a
streamlined feature aggregation network, and reduces the number of detection
heads, thereby eliminating the iterative refinement process. This model uses
CLRNet as a teacher model, incorporating a novel knowledge distillation
procedure to enhance the performance of the streamlined student model and
offset potential declines in detection accuracy. This multi-layered
distillation includes intermediate feature layers, prior embeddings, and
detection head logits, ensuring CLRKDNet achieves a comparable detection
accuracy to CLRNet while operating at a significantly faster speed. For
further details, please see the Method section III.

We validate the advancements of our proposed method through extensive
experiments conducted on the CULane [15] and TuSimple [22] datasets, reporting
state-of-the-art results on both. Additionally, comprehensive ablation studies
confirm the efficacy of each component within our framework. Our principal
contributions are summarized as follows:

  * •

We achieved significant computational efficiency by simplifying the feature
enhancement module and reducing the number of detection heads in CLRNet,
resulting in an increase of up to 60% in inference speed.

  * •

We introduce a novel knowledge distillation technique, wherein our streamlined
student model, CLRKDNet, leverages both the intermediate feature layers, prior
embeddings, and the final detection head logits of the teacher model, CLRNet,
to enhance its lane detection capabilities.

  * •

We conducted extensive experiments across various lane detection datasets to
validate the effectiveness of our proposed method, CLRKDNet, and performed
comprehensive ablation studies to verify the contribution of each module to
the model’s performance.

##  II Related Work

###  II-A Lane Detection

####  II-A1 Segmentation-based Methods

Segmentation-based methods treat lane detection as a pixel-wise classification
task, separating lane line regions from the background. For instance, SCNN
[15] leverages a semantic segmentation framework with a message-passing
mechanism to improve spatial relationships in lane detection, though its real-
time application is limited by speed. Similarly, RESA [30] enhances
performance through a real-time feature aggregation module, yet remains
computationally demanding due to its pixel-level processing.

####  II-A2 Parametric Curve-based Methods

These methods represent lanes using curve parameters, which are then fitted to
lane data. LSTR [10] employs a Transformer architecture to capture both thin,
long lane features and broader road features. PolyLaneNet [21] and other works
[1] utilize polynomial and Bezier curves, respectively, for lane detection,
offering fast inference but sensitive to parameter inaccuracies.

####  II-A3 Keypoint-based Methods

Keypoint-based methods detect lane lines by identifying key points and then
clustering them into lane instances. PINet [6] and similar approaches [23, 18]
use advanced networks and clustering algorithms for this purpose, though
requiring intensive post-processing which increases computational load.

####  II-A4 Anchor-based Methods

Anchor-based methods rely on predefined line or row anchors to guide lane
detection. Line-CNN [8] and LaneATT [20] use line anchors with attention
mechanisms for enhanced accuracy and efficiency. Conversely, row-anchor based
methods like UFLD [16] and CondLaneNet [9] offer simplicity and speed but can
struggle with complex scenarios due to challenges in accurately recognizing
initial lane points. CLRNet [29] and its extension work [4] propose a cross-
layer optimized lane detection network, which detects lane lines using high-
level features and adjusts the lane line position using low-level features.

###  II-B Knowledge Distillation

Knowledge distillation involves transferring insights from a complex, often
cumbersome model to a more compact and computationally efficient one, thereby
enhancing the smaller model’s performance and generalizability. This technique
was initially introduced by Hinton et al. in 2015 [3]. Over the years, it has
diversified into numerous approaches, including the adoption of soft labels
and tailored loss functions to refine learning processes. In computer vision,
knowledge distillation has significantly boosted the capabilities of smaller
models across various tasks such as object detection, image classification,
and segmentation. Specifically within lane detection, Hou et al. introduced
Self-Attention Distillation (SAD) [5], which employs top-down and hierarchical
attention distillation to augment representation learning and model efficacy.
Notably, our distillation approach outperforms SAD, achieving an F1-score on
the CULane dataset that surpasses it by nearly 10 percentage points.

##  III Methods

Figure 2: The upper part of the model represents the teacher’s configuration,
featuring a deeper backbone for feature extraction, three layers of FPN for
feature fusion, and a detection head connected to each FPN layer. The
detection head performs iterative prior refinement, indicated by the dashed
line looping back to the prior parameters. The lower part is the student
network, CLRKDNet, which typically has a lighter backbone, a feature
aggregation module for feature enhancement, and a single detection head for
lane prediction output. During the training process, three types of
distillation are applied: (a) Attention Map Transfer, occurring during multi-
scale feature extraction in the backbone network, transferring attention maps
information from the teacher to the student model; (b) Prior Knowledge
Transfer, transferring the teacher’s refined priors to the student’s initial
priors; and (c) Logits Transfer, comparing the classification and regression
outputs of both models to refine the student’s performance.

###  III-A CLRKDNet

####  III-A1 Teacher Model

Our method utilizes the sophisticated CLRNet[29] architecture as teacher
model, which integrates robust backbones such as ResNet or DLA. This
integration enables the backbone network to extract deep features, which are
then processed by a Feature Pyramid Network (FPN) that generates multi-scale
feature maps at varying resolutions, including $\frac{1}{8},\frac{1}{16},$ and
$\frac{1}{32}$ of the input image size. This approach captures a comprehensive
representation of both global content and local details. CLRNet initiates lane
detection by configuring priors with learnable parameters
$(x^{i},y^{i},\theta^{i})$, where $(x^{i},y^{i})$ define the starting
coordinates and $\theta^{i}$ is the orientation with respect to x-axis. The
symbol $i$ represents one of the priors in a list of $M$ priors, where $M$
denotes the total number of priors. These priors, crucial for identifying
potential lane paths, are processed through multiple convolutional and fully
connected layers across various scales. As shown in Fig. 2, this multi-layer
processing generates classification and regression outputs for prior
adjustments. The model undergoes three refinement cycles where these
adjustments recalibrate the priors, leveraging higher-resolution feature maps
for improved accuracy. Cross-attention mechanisms integrate contextual
information throughout this process, culminating in the precise calculation of
x-coordinates across multiple horizontal rows to delineate lane paths.

To tackle the complexities of lane detection, CLRNet employs a comprehensive
loss function L, combining smooth-L1 for prior refinement, focal loss for
classification, and cross-entropy loss for segmentation. Additionally, a novel
LineIoU loss specifically enhances the intersection-over-union metric for lane
predictions, boosting the model’s precision.

$L=\lambda_{\text{xyl}\theta}L_{\text{xyl}\theta}+\lambda_{\text{cls}}L_{\text{cls}}+\lambda_{\text{seg}}L_{\text{seg}}+\lambda_{\text{LineIoU}}L_{\text{LineIoU}}$
(1)

$L_{xyl\theta}$ denotes the smooth-L1 loss, $L_{cls}$ is the focal loss for
prior classification, $L_{seg}$ is an auxiliary loss aiding segmentation, and
$L_{LaneIoU}$ is the specially designed IOU loss for lane line. The weighting
for this loss function during training could be find in subsection III-D

Figure 3: Illustration of detection head

####  III-A2 Student Model

CLRKDNet is a streamlined variant of the advanced CLRNet model, designed to
meet the demanding requirements of real-time autonomous driving applications
while managing lane detection performance. It leverages CLRNet’s advanced
network design, including its backbone and detection head mechanisms, but
introduces significant optimizations in its architecture to enhance
efficiency.

In the feature enhancement section, where CLRNet integrates multi-scale,
semantically rich features through an FPN, our CLRKDNet deploys a lean feature
aggregation network to reduce computational burden. As shown in Fig. 2, this
network is purpose-built to condense the channel size of the extracted
features from the backbone, enhancing their representational quality without
the computational heft. This innovation not only slashes the number of weight
parameters but also diminishes the computational footprint, enabling a swifter
feature integration process.

The detection head of our CLRKDNet is also optimized for efficiency. Unlike
CLRNet’s multiple detection heads and learnable priors that require intensive
computational resources for iterative refinement, our CLRKDNet adopts a single
detection head with a fixed set of priors. This singular head leverages a set
of static priors without engaging in costly iterative refinement processes.
The structure of a single detection head is shown in Fig. 3. Experimental
analysis shows that this simplification has increased the inference speed of
our CLRKDNnet by up to 60%, while the evaluation scores has only decreased
slightly.

The decrease in detection performance resulting from the simplified
architecture is further compensated by the knowledge distillation. Our
proposed knowledge transfer method leverages distilled insights from the
intermediate layers of the teacher model CLRNet, as well as priors and final
output of the detection head. Through this muti-stage distillation process,
our CLRKDNet model closely approaches the benchmark set by CLRNet while
operating at a fraction of the computational cost.

###  III-B Attention Map Distillation

####  III-B1 Activation Attention Transfer

In our lane detection model, knowledge distillation is facilitated through an
activation-based attention mechanism [27]. For each $n$-th layer of the
convolutional neural network, we extract activation outputs, denoted as
$A_{n}\in\mathbb{R}^{C_{n}\times H_{n}\times W_{n}}$, where $C_{n}$, $H_{n}$,
and $W_{n}$ correspond to the number of channels, height, and width of the
activation tensor, respectively.

To distill knowledge from the teacher model to the student model, we generate
spatial attention maps from these activation tensors. These maps serve as
condensed representations that spotlight the areas within the input image
deemed most critical by the model. These maps are distilled through the
application of a mapping function,
$G_{\text{sum}^{p}}(A_{n})=\sum_{j=1}^{C_{n}}|A_{n,j}|^{p}$, where each
$A_{n,j}$ denotes the $j$-th slice of $A_{n}$ in the channel dimension, and
$p>1$. Drawing from the precedent set by other papers [5], we selected this
$p=2$ to intensify the emphasis on the most distinct features, thereby
directing the student model’s focus in a manner akin to the teacher model. The
process of this Attention Map Distillation is shown in Fig. 2. During the
entire training phase, the attention maps of the student model are
progressively adjusted to match those of the teacher model, with differences
minimized using a loss function.

####  III-B2 Attention Transfer Loss

The distillation of attention maps in our lane detection model is quantified
through an attention transfer loss function that specifically measures the
divergence between the attention maps of the student and teacher models. For
each paired layer indexed by $n$ in the set $N$ (representing indices of every
teacher-student activation layer pairs), the attention maps from the student
model $A_{n}^{S}$ and the teacher model $A_{n}^{T}$ are first transformed into
vectorized forms, denoted as $Q_{n}^{S}$ and $Q_{n}^{T}$, respectively. These
vectorized forms are produced by applying the mapping function $G$ in previous
section to activation tensors and reshaping the resulting attention maps into
vectors.

$L_{att}=\sum_{n\in
N}\left\|\frac{Q_{n}^{S}}{\|Q_{n}^{S}\|_{2}}-\frac{Q_{n}^{T}}{\|Q_{n}^{T}\|_{2}}\right\|_{p}$
(2)

where $Q_{n}^{S}=\textit{vec}(G(A_{n}^{S}))$ and
$Q_{n}^{T}=\textit{vec}(G(A_{n}^{T}))$ are the vectorized forms of the $n$-th
attention map pair between student and teacher model, respectively. The term
$\|\cdot\|_{2}$ denotes the $\ell_{2}$ norm, which is used to normalize each
vectorized attention map, making sure that the loss computation is invariant
to the scale of the attention maps and focuses purely on their patterns. The
parameter $p$ is set to 2, aligning with the use of the second degree mapping
function G in attention map calculation, which has been empirically shown to
facilitate effective knowledge transfer.

###  III-C Knowledge Transfer on Detection Head

Following the attention map distillation process, we aim to further improve
detection accuracy and bridge the gap between the models. To achieve this, we
come up with a dual distillation procedure for the detection head, employing
prior embedding distillation and logits distillation. These mechanisms ensure
that CLRKDNet effectively retains the sophisticated detection capabilities of
its teacher model, CLRNet, despite its streamlined architecture. The prior
embedding distillation aligns the student’s priors with the refined outputs of
the teacher, while logits distillation measures and minimizes the
discrepancies in output logits, guiding CLRKDNet’s predictions to closely
match those of CLRNet.

####  III-C1 Prior Embedding Distillation

Both CLRNet and CLRKDNet initialize their detection heads with embedded priors
that define the geometric parameters of lane lines, including initial
coordinates $(x^{i},y^{i})$ and orientation $\theta^{i}$ relative to the
x-axis. These priors and feature map, generated by the backbone and feature
fusion network, guide the ROI module for accurate gathering of nearby features
for each lane pixel. This gathering process combines global content with rich
semantic information, ensuring comprehensive detection capabilities. While
CLRNet refines these priors across various layers of its detection head,
enhancing them iteratively, CLRKDNet uses a single set of these priors
directly for detection output.

The distillation of these priors is accomplished by comparing the prior
embeddings between the student’s initial priors and the refined priors of the
teacher model. Specifically, the embedding, formatted as a tensor with $[M,3]$
dimension where $M$ represents the number of initial priors, are compared
using an L2 norm loss function:

$L_{\text{prior}}=\sum_{i=1}^{M}\|P_{S}^{i}-P_{T}^{i}\|_{2}$ (3)

Here, $P_{S}^{i}$ and $P_{T}^{i}$ represent the $i$-th prior vectors from the
student and teacher models, respectively, each encompassing the initial
coordinates and orientation $(x^{i},y^{i},\theta^{i})$. This L2 norm
comparison measures the Euclidean distance between each pair of corresponding
priors, effectively aligning CLRKDNet’s static priors with the dynamically
refined priors of CLRNet. This alignment ensures that the student model starts
from a refinement level comparable to the output of the teacher’s iterative
process, effectively bridging the gap in dynamic refinement capabilities
between the two models.

Method | Backbone | F1(%) | FPS | Normal | Crowd | Dazzle | Shadow | Noline | Arrow | Curve | Cross | Night |
---|---|---|---|---|---|---|---|---|---|---|---|---|---
SCNN [15] | VGG16 | 71.60 | 50 | 90.60 | 69.70 | 58.50 | 66.90 | 43.40 | 84.10 | 64.40 | 1990 | 66.10 |
LaneATT [20] | ResNet18 | 75.13 | 250 | 91.17 | 72.71 | 65.82 | 68.03 | 49.13 | 87.82 | 63.75 | 1020 | 68.58 |
LaneATT [20] | ResNet34 | 76.68 | 170 | 92.14 | 75.03 | 64.47 | 78.15 | 49.39 | 88.38 | 67.72 | 1330 | 70.72 |
CondLaneNet [9] | ResNet18 | 78.14 | 348 | 92.87 | 75.79 | 70.72 | 80.01 | 52.39 | 89.37 | 72.40 | 1364 | 73.23 |
CondLaneNet [9] | ResNet34 | 78.74 | 237 | 93.38 | 77.14 | 71.17 | 79.93 | 51.85 | 89.89 | 73.88 | 1387 | 73.92 |
UFLD [16] | ResNet18 | 68.40 | 620 | 87.70 | 66.00 | 58.40 | 62.80 | 40.20 | 81.00 | 57.90 | 1743 | 62.10 |
UFLD [16] | ResNet34 | 72.30 | 340 | 90.70 | 70.20 | 59.50 | 69.30 | 44.40 | 85.70 | 69.50 | 2037 | 66.79 |
SAD [5] | ENet | 70.80 | 200 | 90.10 | 68.80 | 60.20 | 65.90 | 41.60 | 84.00 | 65.70 | 1998 | 66.00 |
SAD [5] | ResNet101 | 71.80 | 40 | 90.70 | 70.00 | 59.90 | 67.00 | 43.50 | 84.40 | 65.70 | 2052 | 66.30 |
UFLDv2 [17] | ResNet18 | 74.70 | 330 | 91.70 | 73.00 | 64.60 | 74.70 | 47.20 | 87.60 | 68.70 | 1998 | 70.20 |
UFLDv2 [17] | ResNet34 | 75.90 | 165 | 92.50 | 74.90 | 65.70 | 75.30 | 49.00 | 88.50 | 70.20 | 1864 | 70.60 |
CLRNet [29] | ResNet18 | 79.58 | 275 | 93.30 | 78.33 | 73.71 | 79.66 | 53.15 | 90.25 | 71.56 | 1321 | 75.11 |
CLRNet [29] | ResNet101 | 80.13 | 46 | 93.85 | 78.78 | 72.49 | 82.33 | 54.50 | 89.79 | 75.57 | 1262 | 75.51 |
CLRNet [29] | DLA34 | 80.47 | 185 | 93.73 | 79.59 | 75.30 | 82.51 | 54.58 | 90.62 | 74.13 | 1155 | 75.37 |
FLAMNet [19] | ResNet34 | 80.15 | 93 | 93.61 | 78.35 | 73.64 | 81.31 | 53.68 | 90.67 | 73.38 | 982 | 75.50 |
FLAMNet [19] | DLA34 | 80.67 | 101 | 93.94 | 79.35 | 77.02 | 82.94 | 54.62 | 90.51 | 75.23 | 1205 | 76.49 |
CLRKDNet (Ours) | ResNet18 | 79.66 | 450 | 93.34 | 78.19 | 74.62 | 80.46 | 52.61 | 89.98 | 69.17 | 904 | 79.66 |
CLRKDNet (Ours) | DLA34 | 80.68 | 265 | 93.86 | 79.95 | 75.63 | 81.88 | 54.85 | 90.42 | 72.81 | 1147 | 75.82 |

TABLE I: Result comparison with state-of-art methods on CULane. FPS is
measured using single NVIDIA 3090 GPU

####  III-C2 Logit Distillation

Logit distillation focuses on the final output of the detection heads before
transforming the model outputs into predicted lines. As shown in Fig.3, such
logits include classification scores and geometric features, such as starting
coordinates $(x^{i},y^{i})$, angles $\theta^{i}$, lane lengths $l^{i}$, and
the horizontal offset differences $\Delta x^{i}$ between the predicted lanes
and the lane priors. The logically distillation process involves comparing
these logical outputs from the student’s detection head against those of the
teacher model and calculating a Mean Squared Error (MSE) to measure and
minimize the differences between them.

This loss ensures that CLRKDNet’s simplified detection head, which lacks the
multiple refinement stages of CLRNet, can still produce outputs with a high
degree of accuracy. The MSE, being sensitive to large discrepancies, is
particularly effective in fine-tuning the student model’s output to closely
mimic those of the teacher, thereby compensating for the absence of iterative
refinement layers. This particular loss is written as:

$\displaystyle L_{\text{logit}}=\frac{1}{M}\sum_{i=1}^{M}\Bigl{(}$
$\displaystyle(x^{i}_{S}-x^{i}_{T})^{2}+(y^{i}_{S}-y^{i}_{T})^{2}$ (4)
$\displaystyle+(\theta^{i}_{S}-\theta^{i}_{T})^{2}+(l^{i}_{S}-l^{i}_{T})^{2}$
$\displaystyle+(\Delta x^{i}_{S}-\Delta x^{i}_{T})^{2}\Bigr{)}$

Where $M$ is the number of priors.
$x^{i}_{S},y^{i}_{S},\theta^{i}_{S},l^{i}_{S},\Delta x^{i}_{S}$ are the
geometric outputs of detection head, including origin coordinates,
orientation, length, and horizontal difference.
$x^{i}_{T},y^{i}_{T},\theta^{i}_{T},l^{i}_{T},\Delta x^{i}_{T}$ are the
corresponding outputs from the teacher model.

###  III-D Training Details

####  III-D1 Training Loss

  * •

Distillation Loss ($L_{\text{dis}}$): The total distillation loss is the sum
of three key losses: attention map transfer loss, lane prior embeddings loss,
and detection head logit loss. This comprehensive loss is formulated as
follows:

$L_{\text{dis}}=w_{\text{att}}L_{\text{att}}+w_{\text{prior}}L_{\text{prior}}+w_{\text{logit}}L_{\text{logit}}$
(5)

The coefficient $w_{\text{att}}$, $w_{\text{prior}}$, $w_{\text{logit}}$
adjusts the impact of the corresponding distillation loss term to optimize the
transfer of knowledge from CLRNet to CLRKDNet. More details about distillation
losses could be found in section IV-C

  * •

Classification and Regression Loss ($L_{\text{CR}}$): For the general loss
calculation, we follow the equation 1 from CLRNet, with the loss weights set
as follows: $\lambda_{\text{xyl}\theta}=0.2$, $\lambda_{\text{cls}}=2$,
$\lambda_{\text{seg}}=1$, and $\lambda_{\text{LineIoU}}=2$.

####  III-D2 Knowledge Distillation Setups

For training on the CULane dataset, CLRKDNet with a ResNet18 backbone was
trained on CLRNet’s ResNet101 backbone model, which achieved an F1-score of
80.13%. Meanwhile, CLRKDNet with a DLA34 backbone was trained on the retrained
CLRNet’s DLA34 backbone model, which attained an F1-score of 80.71% after
removing frame redundancy. For the TuSimple dataset, since ResNet18 had the
best overall performance, we utilized CLRNet with a ResNet18 backbone to train
CLRKDNet, maintaining the same backbone.

Following the paper by Hiroto [4], redundant training data removal was
conducted before training on the CULane dataset. Frames with an average pixel
value difference below a threshold of 15 from the previous frame were
discarded, leaving 55,698 frames (62.7%) for training. This process mitigates
overfitting and enhances CLRKDNet’s baseline F1-score to 79.05% with a
ResNet18 backbone, representing an approximately 0.6% increase from the
baseline score of 78.40% achieved by the model without redundant data removal.
With a DLA34 backbone, the F1-score of our CLRKDNet baseline model is 80.13%
after removing redundant data, which is close to the teacher model CLRNet’s
score of 80.47%. After retraining CLRNet with redundant data removal, we
achieve an F1-score of 80.71%, establishing this as our new teacher model
weight.

##  IV EXPERIMENTS

###  IV-A Datasets

####  IV-A1 CULane

[15] is an extensive dataset encompassing 88,880 training images and 34,680
test images, all formatted at a resolution of 1640x590 pixels. It covers a
wide range of driving conditions, including urban and highway scenes, and
categorizes test images into scenarios like night, crowded, and curved lanes.

####  IV-A2 TuSimple

[22] focuses on highway scenes and includes 3,268 training images, 358
validation images, and 2,782 testing images, each with a resolution of
1280x720 pixels.

###  IV-B Evaluation Metrics

The efficacy of lane detection methods in our study is quantified through the
metrics of Accuracy (Acc) and the F1-score.

####  IV-B1 Accuracy (Acc)

Acc quantifies the proportion of correctly identified lane points. A
prediction is deemed accurate if over 85% of the predicted points fall within
20 pixels of the ground truth lane markers [22]. The accuracy metric is
computed as:

$Acc=\frac{\sum_{\textit{clip}}C_{\textit{clip}}}{\sum_{\textit{clip}}S_{\textit{clip}}}.$
(6)

where $C_{\text{clip}}$ represents the number of points within the 20-pixel
boundary of the ground truth, and $S_{\text{clip}}$ is the total count of lane
points in the image.

####  IV-B2 F1-score

It is used to understand the balance between precision and recall, where
predictions with an Intersection over Union (IoU) greater than a set threshold
are considered as true positives (TP) [15]. It is calculated by the formula:

$F1=\frac{2\times\textit{Precision}\times\textit{Recall}}{\textit{Precision}+\textit{Recall},}$
(7)

where the Precision and Recall are determined by:

$\textit{Precision}=\frac{TP}{TP+FP},$ (8) $\textit{Recall}=\frac{TP}{TP+FN},$
(9)

with $TP$ representing true positives, $FP$ denoting false positives, and $FN$
indicating false negatives.

Method | Backbone | F1 | FPS
---|---|---|---
SAD [5] | ENet | 70.80 | 200
SAD [5] | ResNet101 | 71.80 | 40
CLRKDNet (Ours) | ResNet18 | 79.66 | 450
CLRKDNet (Ours) | DLA34 | 80.68 | 265
TABLE II: Performance comparison of different lane detection methods that
utilize knowledge transfer

###  IV-C Implementation Details

In this study, we employ knowledge distillation techniques with teacher and
student models based on ResNet [2] and DLA [26] architectures, pre-trained on
ImageNet. Input images are resized to a consistent resolution of $320\times
800$ for uniform processing. Following established methods [29][9][18], data
augmentation such as random affine transformation and random horizontal flip
were employed. Model optimization utilizes the AdamW [11] optimizer with a
cosine decay learning rate strategy [12], calibrated to initial values of
$1\times 10^{-3}$. Training duration are set at 20 epochs for the CULane
dataset and 90 epochs for the TuSimple dataset, tailored to each dataset’s
complexity.

The teacher model utilizes the original CLRNet implementation, ensuring robust
lane detection capabilities. All computational tasks are executed on a single
RTX 3090 GPU using PyTorch. The weighted loss of distillation loss calculation
in equation 5 is set as follows: $w_{\text{att}}=1$, $w_{\text{prior}}=3$,
$w_{\text{logit}}=5$. The number of initial priors $M$ = 192 and paired
activate layer $N$ is set to 4.

###  IV-D Experimental Results

####  IV-D1 Performance on CULane

We present our model’s benchmark results on the CULane dataset, alongside
other state-of-the-art models, in Table I. Our proposed method, CLRKDNet,
achieves an F1-score of 79.66% with a ResNet18 backbone, marking a 0.08%
increase over CLRNet’s score of 79.58% with the same backbone. Additionally,
the inference speed has increased from 275 FPS to 450 FPS, an impressive 60%
improvement. With a DLA34 backbone, after removing frame redundancy and
retraining the original CLRNet model, it attains an F1-score of 80.71%.
Meanwhile, CLRKDNet records an F1-score of 80.68%, a minor decrease of 0.03%.
However, CLRKDNet’s inference speed increases by approximately 80 FPS compared
to the CLRNet model, from 185 FPS to 265 FPS, resulting in a 40% increase in
inference speed.

In table II, we compare the F1-score of our model to the only other model in
the field of lane detection that employs distillation. The results reveal that
our model outperforms the SAD [5] model in both detection accuracy and
inference speed. Despite utilizing a similarly lightweight backbone, our model
nearly doubles the inference speed, and the F1-score sees an increase of
almost 10%, rising from 70.80% to 79.66%.

We also present a diagram in Fig. 1 that compares each state-of-the-art
model’s F1-score against its respective inference speed (FPS). The diagram
highlights the balance struck by our model, CLRKDNet, between accuracy and
speed. It outperforms other models in its class, achieving an additional
100-200 FPS compared to similarly performing models. The only model exhibiting
higher efficiency, UFLD, achieves a significantly lower F1-score, with nearly
a 10% deficit compared to CLRKDNet. The visualized comparison between CLRKDNet
and CLRNet is presented in Fig. 4. As shown in the figure, our model,
CLRKDNet, achieves better results in certain categories, such as crowd
circumstances, particularly in columns (b) and (d).

Figure 4: Selected results comparing the CLRNet teacher model with CLRKDNet
student model against ground truth annotation and input images. Certain
category where the student surpasses the teacher’s model is shown with dotted
circle representing the missing detected lane.

####  IV-D2 Performance on TuSimple

Table III showcases the performance of our model alongside state-of-the-art
approaches in TuSimple dataset. Our model, CLRKDNet, demonstrates near-parity
with its teacher model, CLRNet, with only a 0.11% drop in F1-score and a 0.07%
drop in accuracy. Despite this minimal reduction in performance metrics, our
CLRKDNet achieves a runtime more than 50% faster than its teacher model,
aligning with the significant improvements observed in the CULane dataset
experiments.

Method | Backbone | F1(%) | Acc(%) | FP(%) | FN(%) | RT(ms)
---|---|---|---|---|---|---
SCNN [15] | VGG16 | 95.97 | 96.53 | 6.17 | 1.80 | 20
UFLD [16] | ResNet18 | 87.87 | 95.82 | 19.05 | 3.92 | 1.7
UFLD [16] | ResNet34 | 88.02 | 95.86 | 18.91 | 3.75 | 3.0
LaneATT [20] | ResNet18 | 96.71 | 95.57 | 3.56 | 3.01 | 4.0
LaneATT [20] | ResNet34 | 96.77 | 95.63 | 3.53 | 2.92 | 5.9
CondLaneNet [9] | ResNet18 | 97.01 | 95.48 | 2.18 | 3.80 | 2.9
CondLaneNet [9] | ResNet34 | 96.98 | 95.37 | 2.20 | 3.82 | 4.2
UFLDv2 [17] | ResNet18 | 96.16 | 95.65 | 3.06 | 4.61 | 3.2
UFLDv2 [17] | ResNet34 | 96.22 | 95.56 | 3.18 | 4.37 | 5.9
CLRNet [29] | ResNet18 | 97.89 | 96.84 | 2.28 | 1.92 | 3.7
CLRNet [29] | ResNet34 | 97.82 | 96.87 | 2.27 | 2.08 | 4.9
CLRKDNet (Ours) | ResNet18 | 97.78 | 96.80 | 2.43 | 1.92 | 2.4
TABLE III: Performance comparison on TuSimple dataset

###  IV-E Ablation Study and Analysis

To validate the effectiveness of different components in our proposed method,
we conducted an extensive experiment on the CULane dataset. We first evaluated
CLRKDNet’s standalone performance without distillation. This base model
achieved an F1-score of 79.05% and 80.13% for the ResNet18 and DLA34
backbones, respectively, after accounting for frame redundancy removal.

Table IV highlights the progressive improvements as various distillation
losses are integrated into CLRKDNet, guiding the student model to learn from
its teacher. For the ResNet18 backbone, the F1-score improves by 0.61%,
reaching 79.66% when all distillation losses are applied. For the DLA34
backbone, the F1-score increases by 0.55%, culminating at 80.68%.

The differential increases between these backbones can be attributed to the
depth difference during the distillation process. A deeper ResNet101 model
provides more accurate distillation targets for CLRKDNet with a ResNet18
backbone, resulting in a larger performance gain compared to the DLA-based
distillation, where a DLA34 teacher model is used to distill a DLA34 backboned
student model.

Backbone | $L_{\textit{att}}$ | $L_{\textit{logit}}$ | $L_{\textit{prior}}$ | F1
---|---|---|---|---
ResNet18 |  |  |  | 79.05
ResNet18 | ✓ |  |  | 79.31
ResNet18 | ✓ | ✓ |  | 79.52
ResNet18 | ✓ | ✓ | ✓ | 79.66
DLA34 |  |  |  | 80.13
DLA34 | ✓ |  |  | 80.39
DLA34 | ✓ | ✓ |  | 80.54
DLA34 | ✓ | ✓ | ✓ | 80.68
TABLE IV: Ablation study with various distillations losses.

##  V CONCLUSIONS

This paper presents CLRKDNet, a streamlined lane detection model that
effectively balances accuracy and efficiency through architectural refinements
and knowledge distillation techniques. Our experiments on the CULane dataset
demonstrate that CLRKDNet maintains competitive F1-score of 79.66% and 80.68%
for ResNet18 and DLA34 backbones, respectively, while significantly improving
inference speed by up to 60%. These results highlight how the integration of
distillation losses, including prior embedding distillation, attention map
distillation, and logit distillation, allows CLRKDNet to replicate the
sophisticated detection capabilities of its teacher model, CLRNet, despite its
simplified design. This balance between accuracy and efficiency makes CLRKDNet
a viable solution for real-time lane detection in autonomous driving
applications.

## References

  * [1] Zhengyang Feng et al.  “Rethinking efficient lane detection via curve modeling”  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 17062–17070
  * [2] Kaiming He, Xiangyu Zhang, Shaoqing Ren and Jian Sun  “Deep Residual Learning for Image Recognition”  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016
  * [3] Geoffrey Hinton, Oriol Vinyals and Jeff Dean  “Distilling the knowledge in a neural network”  In _arXiv preprint arXiv:1503.02531_ , 2015
  * [4] Hiroto Honda and Yusuke Uchida  “CLRerNet: improving confidence of lane detection with LaneIoU”  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2024
  * [5] Yuenan Hou, Zheng Ma, Chunxiao Liu and Chen Change Loy  “Learning lightweight lane detection cnns by self attention distillation”  In _Proceedings of the IEEE/CVF international conference on computer vision_ , 2019, pp. 1013–1021
  * [6] Yeongmin Ko et al.  “Key points estimation and point instance segmentation approach for lane detection”  In _IEEE Transactions on Intelligent Transportation Systems_ 23.7 IEEE, 2021, pp. 8949–8958
  * [7] Alex Krizhevsky, Ilya Sutskever and Geoffrey E Hinton  “Imagenet classification with deep convolutional neural networks”  In _Advances in neural information processing systems_ 25, 2012
  * [8] Xiang Li, Jun Li, Xiaolin Hu and Jian Yang  “Line-cnn: End-to-end traffic line detection with line proposal unit”  In _IEEE Transactions on Intelligent Transportation Systems_ IEEE, 2019
  * [9] Lizhe Liu, Xiaohao Chen, Siyu Zhu and Ping Tan  “Condlanenet: a top-to-down lane detection framework based on conditional convolution”  In _Proceedings of the IEEE/CVF international conference on computer vision_ , 2021, pp. 3773–3782
  * [10] Ruijin Liu, Zejian Yuan, Tie Liu and Zhiliang Xiong  “End-to-end lane shape prediction with transformers”  In _Proceedings of the IEEE/CVF winter conference on applications of computer vision_ , 2021, pp. 3694–3702
  * [11] Ilya Loshchilov and Frank Hutter  “Decoupled weight decay regularization”  In _arXiv preprint arXiv:1711.05101_ , 2017
  * [12] Ilya Loshchilov and Frank Hutter  “Sgdr: Stochastic gradient descent with warm restarts”  In _arXiv preprint arXiv:1608.03983_ , 2016
  * [13] Fulong Ma et al.  “Every Dataset Counts: Scaling up Monocular 3D Object Detection with Joint Datasets Training”, 2023  arXiv:2310.00920 [cs.CV]
  * [14] Fulong Ma et al.  “Monocular 3D lane detection for Autonomous Driving: Recent Achievements, Challenges, and Outlooks”  In _arXiv preprint arXiv:2404.06860_ , 2024
  * [15] Xingang Pan et al.  “Spatial as deep: Spatial cnn for traffic scene understanding”  In _Proceedings of the AAAI conference on artificial intelligence_ , 2018
  * [16] Zequn Qin, Huanyu Wang and Xi Li  “Ultra fast structure-aware deep lane detection”  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XXIV 16_ , 2020, pp. 276–291  Springer
  * [17] Zequn Qin, Pengyi Zhang and Xi Li  “Ultra fast deep lane detection with hybrid anchor driven ordinal classification”  In _IEEE transactions on pattern analysis and machine intelligence_ IEEE, 2022
  * [18] Zhan Qu et al.  “Focus on local: Detecting lane marker from bottom up via key point”  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2021, pp. 14122–14130
  * [19] Hao Ran, Yunfei Yin, Faliang Huang and Xianjian Bao  “Flamnet: A flexible line anchor mechanism network for lane detection”  In _IEEE Transactions on Intelligent Transportation Systems_ IEEE, 2023
  * [20] Lucas Tabelini et al.  “Keep your eyes on the lane: Real-time attention-guided lane detection”  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2021, pp. 294–302
  * [21] Lucas Tabelini et al.  “Polylanenet: Lane estimation via deep polynomial regression”  In _2020 25th International Conference on Pattern Recognition (ICPR)_ , 2021, pp. 6150–6156  IEEE
  * [22] TuSimple  “Tusimple-benchmark”  In _GitHub_ , 2017  URL: https://github.com/TuSimple/tusimple-benchmark
  * [23] Jinsheng Wang et al.  “A keypoint-based global association network for lane detection”  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 1392–1401
  * [24] Ze Wang, Weiqiang Ren and Qiang Qiu  “Lanenet: Real-time lane detection networks for autonomous driving”  In _arXiv preprint arXiv:1807.01726_ , 2018
  * [25] Chunyu Wei et al.  “Row anchor selection classification method for early-stage crop row-following”  In _Computers and Electronics in Agriculture_ 192 Elsevier, 2022
  * [26] Fisher Yu, Dequan Wang, Evan Shelhamer and Trevor Darrell  “Deep layer aggregation”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 2403–2412
  * [27] Sergey Zagoruyko and Nikos Komodakis  “Paying more attention to attention: Improving the performance of convolutional neural networks via attention transfer”  In _arXiv preprint arXiv:1612.03928_ , 2016
  * [28] Youcheng Zhang et al.  “Deep learning in lane marking detection: A survey”  In _IEEE Transactions on Intelligent Transportation Systems_ 23.7 IEEE, 2021, pp. 5976–5992
  * [29] Tu Zheng et al.  “Clrnet: Cross layer refinement network for lane detection”  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2022, pp. 898–907
  * [30] Tu Zheng et al.  “Resa: Recurrent feature-shift aggregator for lane detection”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 35.4, 2021, pp. 3547–3554


we can employ Theorem 6.5 in the following.

Let $(\mathcal{P}_{1},\ldots,\mathcal{P}_{k})$ be an arbitrary, but fixed path
in the congruence graph ${\mathcal{G}}_{\equiv}$, let
$\mathcal{Q}=\bigcup_{i=1}^{k}\mathcal{P}_{i}$, and let $d$ denote the maximum
of the degrees of the used RMIs. Due to Theorem 6.5 there exists
$c\in\mathbb{N}$ such that:

${\mathsf{dh}}(t^{\sharp},\mathrel{\mathrel{\to}_{\mathcal{Q}\cup\operatorname{\mathcal{U}}(\mathcal{Q})}})\leqslant(1+\operatorname{\operatorname{\Delta}}(\mathcal{A}_{\bar{P}},\mathcal{Q}))\cdot{\mathsf{dh}}(t^{\sharp},\mathrel{\mathrel{\to}_{\mathcal{Q}/\operatorname{\mathcal{U}}(\mathcal{Q})}})+c\cdot\lvert
t\rvert^{d}\hbox to0.0pt{$\;$.\hss}$

Due to Theorem 7.14 it suffices to consider a derivation $A$ based on the path
$(\mathcal{P}_{1},\ldots,\mathcal{P}_{k})$. Suppose $A\colon
s\mathrel{\to^{n}_{\mathcal{Q}/\operatorname{\mathcal{U}}(\mathcal{Q})}}t$.
Then $A$ can be represented as follows:

$s=s_{0}\mathrel{\to^{n_{1}}_{\mathcal{P}_{1}/\operatorname{\mathcal{U}}(\mathcal{P}_{1})}}s_{n_{1}}\mathrel{\to^{n_{2}}_{\mathcal{P}_{2}/{\operatorname{\mathcal{U}}(\mathcal{P}_{1})\cup\operatorname{\mathcal{U}}(\mathcal{P}_{2})}}}\cdots\mathrel{\to^{n_{k}}_{\mathcal{P}_{k}/{\operatorname{\mathcal{U}}(\mathcal{P}_{1})\cup\cdots\cup\operatorname{\mathcal{U}}(\mathcal{P}_{k})}}}s_{n}=t\hbox
to0.0pt{$\;$,\hss}$

such that $n=\sum_{i=1}^{k}n_{i}$. It is sufficient to bound each $n_{i}$ from
the above. Fix $i\in\\{1,\dots,k\\}$. Consider the subderivation

$A^{\prime}\colon
s=s_{0}\mathrel{\to^{n_{1}}_{\mathcal{P}_{1}/\operatorname{\mathcal{U}}(\mathcal{P}_{1})}}s_{n_{1}}\cdots\mathrel{\to^{n_{i}}_{\mathcal{P}_{k}/{\operatorname{\mathcal{U}}(\mathcal{P}_{1})\cup\cdots\cup\operatorname{\mathcal{U}}(\mathcal{P}_{i})}}}s_{n_{i}}\hbox
to0.0pt{$\;$.\hss}$

Then $A^{\prime}$ is contained in $A^{\prime\prime}\colon
s\mathrel{\mathrel{\to}_{\mathcal{P}_{1}\cup\cdots\cup\mathcal{P}_{i-1}\cup\operatorname{\mathcal{U}}(\mathcal{P}_{1})\cup\cdots\operatorname{\mathcal{U}}(\mathcal{P}_{i})}^{\ast}}\cdot\mathrel{\to^{n_{i}}_{\mathcal{P}_{k}/{\operatorname{\mathcal{U}}(\mathcal{P}_{1})\cup\cdots\cup\operatorname{\mathcal{U}}(\mathcal{P}_{i})}}}s_{n_{i}}$.
Let $\hat{P_{i}}\mathrel{:=}(\mathcal{P}_{1},\ldots,\mathcal{P}_{i})$. By
assumption there exists a $\mu$-monotone complexity pair
$(\mathrel{{\succcurlyeq}_{\mathcal{B}_{\hat{P_{i}}}}},\mathrel{{\succ}_{\mathcal{B}_{\hat{P_{i}}}}})$
such that
$\mathcal{P}_{1}\cup\cdots\cup\mathcal{P}_{i-1}\cup\operatorname{\mathcal{U}}(\mathcal{P}_{1}\cup\cdots\cup\mathcal{P}_{i})\subseteq{\mathrel{{\succcurlyeq}_{\mathcal{B}_{\hat{P_{i}}}}}}$
and $\mathcal{P}_{i}\subseteq{\mathrel{{\succ}_{\mathcal{B}_{\hat{P_{i}}}}}}$.
Hence, we obtain
$n_{i}\leqslant([\alpha_{0}]_{\mathcal{B}_{\hat{P_{i}}}}(s))_{1}$ and in sum
${n}\leqslant{k\cdot\lvert s\rvert^{d}}$. Finally, defining the polynomial $p$
as follows:

$p(x)\mathrel{:=}(1+\operatorname{\operatorname{\Delta}}(\mathcal{A}_{\bar{P}},\mathcal{Q}))\cdot
k\cdot x^{d}+c\cdot x^{d}\hbox to0.0pt{$\;$,\hss}$

we conclude
${\mathsf{dh}}(t^{\sharp},\mathrel{\mathrel{\to}_{\mathcal{Q}\cup\operatorname{\mathcal{U}}(\mathcal{Q})}})\leqslant
p(\lvert t\rvert)$. Note that the polynomial $p$ depends only on the algebras
$\mathcal{A}_{\bar{P}}$ and $\mathcal{B}_{\hat{P_{1}}}$, …,
$\mathcal{B}_{\bar{P_{k}}}$.

As the path $(\mathcal{P}_{1},\ldots,\mathcal{P}_{k})$ was chosen arbitrarily,
there exists a polynomial $q$, depending only on the employed RMIs such that
$\operatorname{\mathsf{L}}(t)\leqslant q(\lvert t\rvert)$. Thus the corollary
follows due to Theorem 7.14. ∎

Let $t$ be an arbitrary term. By definition the set in
$\operatorname{\mathsf{L}}(t)$ may consider
$2^{\operatorname{\mathsf{O}}(n)}$-many paths, where $n$ denotes the number of
nodes in ${\mathcal{G}}_{\equiv}$. However, it suffices to restrict the
definition on page 7.5 to _maximal_ paths. For this refinement
$\operatorname{\mathsf{L}}(t)$ contains at most $n^{2}$ paths. This fact we
employ in implementing the WDG method.

######  Example 7.16 (continued from Example 7.5).

For ${\operatorname{\mathsf{WDG}}(\mathcal{R}_{\mathsf{gcd}})}_{\equiv}$ the
above set consists of 8 paths: $(\\{13\\})$, $(\\{13\\},\\{11\\})$,
$(\\{13\\},\\{12\\})$, $(\\{15\\})$, $(\\{15\\},\\{14\\})$, $(\\{17\\})$,
$(\\{18,19,20\\})$, and $(\\{18,19,20\\},\\{16\\})$. In the following we only
consider the last three paths, since all other paths are similarly handled.

  * •

Consider $(\\{17\\})$. Note
$\operatorname{\mathcal{U}}(\\{17\\})=\varnothing$. By taking an arbitrary SLI
$\mathcal{A}$ and the linear restricted interpretation $\mathcal{B}$ with
$\mathsf{gcd}^{\sharp}_{\mathcal{B}}(x,y)=x$ and
$\mathsf{s}_{\mathcal{B}}(x)=x+1$, we have
$\varnothing\subseteq{>_{\mathcal{A}}}$,
$\varnothing\subseteq{\geqslant_{\mathcal{B}}}$, and
$\\{17\\}\subseteq{>_{\mathcal{B}}}$.

  * •

Consider $(\\{18,19,20\\})$. Note
$\operatorname{\mathcal{U}}(\\{18,19,20\\})=\\{1,\ldots,5\\}$. The following
RMI $\mathcal{A}$ is adequate for $(\\{18,19,20\\})$ and strictly monotone on
${\mu}^{\mathcal{P}\cup\operatorname{\mathcal{U}}(\mathcal{P})}_{\mathsf{f}}$.
The presentation of $\mathcal{A}$ is succinct as only the signature of the
usable rules $\\{1,\ldots,5\\}$ is of interest.

$\displaystyle\mathsf{true}_{\mathcal{A}}$
$\displaystyle=\mathsf{false}_{\mathcal{A}}=\mathsf{0}_{\mathcal{A}}=\vec{0}$
$\displaystyle\mathsf{s}_{\mathcal{A}}(\vec{x})$
$\displaystyle=\begin{pmatrix}1&1\\\
0&1\end{pmatrix}\vec{x}+\begin{pmatrix}3\\\ 1\end{pmatrix}$
$\displaystyle{\leqslant}_{\mathcal{A}}(\vec{x},\vec{y})$
$\displaystyle=\begin{pmatrix}0&1\\\
0&0\end{pmatrix}\vec{y}+\begin{pmatrix}1\\\ 3\end{pmatrix}$
$\displaystyle{-}_{\mathcal{A}}(\vec{x},\vec{y})$
$\displaystyle=\vec{x}+\begin{pmatrix}2\\\ 3\end{pmatrix}\hbox
to0.0pt{$\;$.\hss}$

Further, consider the RMI $\mathcal{B}$ giving rise to the complexity pair
$({\mathrel{{\succcurlyeq}_{\mathcal{B}}}},{\mathrel{{\succ}_{\mathcal{B}}}})$.

$\displaystyle\mathsf{0}_{\mathcal{B}}$
$\displaystyle=\makebox[0.0pt][l]{$\mathsf{true}_{\mathcal{B}}=\mathsf{false}_{\mathcal{B}}=\mathsf{\leqslant}_{\mathcal{B}}(\vec{x},\vec{y})=\vec{0}$}$
$\displaystyle\mathsf{s}_{\mathcal{B}}(\vec{x})$
$\displaystyle=\begin{pmatrix}1&3\\\
0&0\end{pmatrix}\vec{x}+\begin{pmatrix}3\\\ 0\end{pmatrix}$
$\displaystyle{-}_{\mathcal{B}}(\vec{x},\vec{y})$
$\displaystyle=\begin{pmatrix}1&0\\\
2&2\end{pmatrix}\vec{x}+\begin{pmatrix}0&0\\\ 1&0\end{pmatrix}$
$\displaystyle\mathsf{if_{gcd}}^{\sharp}_{\mathcal{B}}(x,y,z)$
$\displaystyle=\begin{pmatrix}3&0\\\
0&0\end{pmatrix}\vec{y}+\begin{pmatrix}3&0\\\ 0&0\end{pmatrix}\vec{z}$
$\displaystyle\mathsf{gcd}^{\sharp}_{\mathcal{B}}(x,y)$
$\displaystyle=\makebox[0.0pt][l]{$\begin{pmatrix}3&0\\\
0&0\end{pmatrix}\vec{x}+\begin{pmatrix}3&0\\\
0&0\end{pmatrix}\vec{y}+\begin{pmatrix}2\\\ 0\end{pmatrix}$ \hbox
to0.0pt{$\;$.\hss}}$

We obtain $\\{1,\ldots,5\\}\subseteq{\mathrel{{\succ}_{\mathcal{A}}}}$,
$\\{1,\ldots,5\\}\subseteq{\mathrel{{\succcurlyeq}_{\mathcal{B}}}}$, and
$\\{18,19,20\\}\subseteq{\mathrel{{\succ}_{\mathcal{B}}}}$.

  * •

Consider $(\\{18,19,20\\},\\{16\\})$. Note
$\operatorname{\mathcal{U}}(\\{16\\})=\varnothing$. By taking the same
$\mathcal{A}$ and also $\mathcal{B}$ as above, we have
$\\{1,\ldots,5\\}\subseteq{\mathrel{{\succ}_{\mathcal{A}}}}$,
$\\{1,\ldots,5,18,19,20\\}\subseteq{\mathrel{{\succcurlyeq}_{\mathcal{B}}}}$,
and $\\{16\\}\subseteq{\mathrel{{\succ}_{\mathcal{B}}}}$.

Thus, all path constraints are handled by suitably defined RMIs of dimension
2. Hence, the runtime complexity function of $\mathcal{R}_{\mathsf{gcd}}$ is
at most quadratic, which is unfortunately not optimal, as
$\mathsf{rc}_{\mathcal{R}_{\mathsf{gcd}}}$ is linear.

Corollary 7.15 is more powerful than Corollary 6.14. We illustrate it with a
small example.

######  Example 7.17.

Consider the TRS $\mathcal{R}$

$\displaystyle\mathsf{f}(\mathsf{a},\mathsf{s}(x),y)$
$\displaystyle\to\mathsf{f}(\mathsf{a},x,\mathsf{s}(y))$
$\displaystyle\mathsf{f}(\mathsf{b},x,\mathsf{s}(y))$
$\displaystyle\to\mathsf{f}(\mathsf{b},\mathsf{s}(x),y)\hbox
to0.0pt{$\;$.\hss}$

Its weak dependency pairs $\operatorname{\mathsf{WDP}}(\mathcal{R})$ are

$\displaystyle 1\colon\leavevmode\nobreak\
\mathsf{f}^{\sharp}(\mathsf{a},\mathsf{s}(x),y)$
$\displaystyle\to\mathsf{f}^{\sharp}(\mathsf{a},x,\mathsf{s}(y))$
$\displaystyle 2\colon\leavevmode\nobreak\
\mathsf{f}^{\sharp}(\mathsf{b},x,\mathsf{s}(y))$
$\displaystyle\to\mathsf{f}^{\sharp}(\mathsf{b},\mathsf{s}(x),y)\hbox
to0.0pt{$\;$.\hss}$

The corresponding congruence graph consists of the two isolated nodes
$\\{1\\}$ and $\\{2\\}$. It is not difficult to find suitable $1$-dimensional
RMIs for the nodes, and therefore
$\mathsf{rc}_{\mathcal{R}}(n)=\operatorname{\mathsf{O}}(n)$ is concluded. On
the other hand, it can be verified that the linear runtime complexity cannot
be obtained by Corollary 6.14 with a $1$-dimensional RMI.

We conclude this section with a brief comparison of the path analysis
developed here and the use of the dependency graph refinement in termination
analysis. First we recall a theorem on the dependency graph refinement in
conjunction with usable rules and innermost rewriting (see [24], but also
[25]). Similar results hold in the context of full rewriting, see [21, 22].

######  Theorem 7.18 ([24]).

A TRS $\mathcal{R}$ is innermost terminating if for every maximal cycle
$\mathcal{C}$ in the dependency graph
$\operatorname{\mathsf{DG}}(\mathcal{R})$ there exists a reduction pair
$(\gtrsim,\succ)$ such that
${\operatorname{\mathcal{U}}(\mathcal{C})}\subseteq{\gtrsim}$ and
${\mathcal{C}}\subseteq{\succ}$.

The following example shows that in the context of complexity analysis it is
_not_ sufficient to consider each cycle individually.

######  Example 7.19 (continued from Example 6.9).

Consider the TRS $\mathcal{R}_{\mathsf{exp}}$ introduced in Example 6.9.

$\displaystyle\mathsf{exp}(\mathsf{0})$
$\displaystyle\to\mathsf{s}(\mathsf{0})$ $\displaystyle\mathsf{d}(\mathsf{0})$
$\displaystyle\to\mathsf{0}$ $\displaystyle\mathsf{exp}(\mathsf{r}(x))$
$\displaystyle\to\mathsf{d}(\mathsf{exp}(x))$
$\displaystyle\mathsf{d}(\mathsf{s}(x))$
$\displaystyle\to\mathsf{s}(\mathsf{s}(\mathsf{d}(x)))\hbox
to0.0pt{$\;$.\hss}$

Recall that the (innermost) runtime complexity of $\mathcal{R}_{\mathsf{exp}}$
is exponential. Let $\mathcal{P}$ denote the (standard) dependency pairs with
respect to $\mathcal{R}_{\mathsf{exp}}$. Then $\mathcal{P}$ consists of three
pairs:
$1\colon\mathsf{exp}^{\sharp}(\mathsf{r}(x))\to\mathsf{d}^{\sharp}(\mathsf{exp}(x))$,
$2\colon\mathsf{exp}^{\sharp}(\mathsf{r}(x))\to\mathsf{exp}^{\sharp}(x)$, and
$3\colon\mathsf{d}^{\sharp}(\mathsf{s}(x))\to\mathsf{d}^{\sharp}(x)$. Hence
the dependency graph $\operatorname{\mathsf{DG}}(\mathcal{R}_{\mathsf{exp}})$
contains two maximal cycles: $\\{2\\}$ and $\\{3\\}$.

We define two reduction pairs
$(\mathrel{{\succcurlyeq}_{\mathcal{A}}},\mathrel{{\succ}_{\mathcal{A}}})$ and
$(\mathrel{{\succcurlyeq}_{\mathcal{B}}},\mathrel{{\succ}_{\mathcal{B}}})$
such that the conditions of the theorem are fulfilled. Let $\mathcal{A}$ and
$\mathcal{B}$ be SLIs such that $\mathsf{exp}^{\sharp}_{\mathcal{A}}(x)=x$,
$\mathsf{r}_{\mathcal{A}}(x)=x+1$ and
$\mathsf{d}^{\sharp}_{\mathcal{B}}(x)=x$, $\mathsf{s}_{\mathcal{A}}(x)=x+1$.
Hence for any term $t\in\operatorname{\mathcal{T}_{\mathsf{b}}}$, we have that
the derivation heights
${\mathsf{dh}}(t^{\sharp},\mathrel{\mathrel{\smash{\xrightarrow{\raisebox{-2.84526pt}{\tiny{$\mathrm{i}$}}}}}_{\\{2\\}/\operatorname{\mathcal{U}}(\mathcal{P})}})$
and
${\mathsf{dh}}(t^{\sharp},\mathrel{\mathrel{\smash{\xrightarrow{\raisebox{-2.84526pt}{\tiny{$\mathrm{i}$}}}}}_{\\{3\\}/\operatorname{\mathcal{U}}(\mathcal{P})}})$
are linear in $\lvert t\rvert$, while
${\mathsf{dh}}(t,\mathrel{\mathrel{\smash{\xrightarrow{\raisebox{-2.84526pt}{\tiny{$\mathrm{i}$}}}}}_{\mathcal{R}}})$
is (at least) exponential in $\lvert t\rvert$.

Observe that the problem exemplified by Example 7.19 cannot be circumvented by
replacing the dependency graph employed in Theorem 7.18 with weak (innermost)
dependency graphs. The exponential derivation height of terms $t_{n}$ in
Example 7.19 is not controlled by the cycles $\\{2\\}$ or $\\{3\\}$, but
achieved through the non-cyclic pair $1$ and its usable rules.

Example 7.19 shows an exponential speed-up between the maximal number of
dependency pair steps within a cycle in the dependency graph and the runtime
complexity of the initial TRS. In the context of derivational complexity this
speed-up may even increase to a primitive recursive function, cf. [23].

While Example 7.19 shows that the usable rules need to be taken into account
fully for any complexity analysis, it is perhaps tempting to think that it
should suffice to demand that at least one weak (innermost) dependency pair in
each cycle decreases strictly. However this intuition is deceiving as shown by
the next example.

######  Example 7.20.

Consider the TRS $\mathcal{R}$ of
$\mathsf{f}(\mathsf{s}(x),\mathsf{0})\to\mathsf{f}(x,\mathsf{s}(0))$ and
$\mathsf{f}(x,\mathsf{s}(y))\to\mathsf{f}(x,y)$.
$\operatorname{\mathsf{WDP}}(\mathcal{R})$ consists of
$1\colon\mathsf{f}^{\sharp}(\mathsf{s}(x),\mathsf{0})\to\mathsf{f}^{\sharp}(x,\mathsf{s}(x))$
and $2\colon\mathsf{f}^{\sharp}(x,\mathsf{s}(y))\to\mathsf{f}^{\sharp}(x,y)$,
and the weak dependency graph $\operatorname{\mathsf{WDG}}(\mathcal{R})$
contains two cycles $\\{1,2\\}$ and $\\{2\\}$. There are two linear restricted
interpretations $\mathcal{A}$ and $\mathcal{B}$ such that
$\\{1,2\\}\subseteq{\geqslant_{\mathcal{A}}}\cup{>_{\mathcal{A}}}$,
$\\{1\\}\subseteq{>_{\mathcal{A}}}$, and $\\{2\\}\subseteq{>_{\mathcal{B}}}$.
Here, however, we must not conclude linear runtime complexity, because the
runtime complexity of $\mathcal{R}$ is at least quadratic.

##  8 Experiments

All described techniques have been incorporated into the _Tyrolean Complexity
Tool_ TCT, an open source complexity analyser666Available at http://cl-
informatik.uibk.ac.at/software/tct.. The testbed is based on version 8.0.2 of
the _Termination Problems Database_ (_TPDB_ for short). We consider TRSs
without theory annotation, where the runtime complexity analysis is non-
trivial, that is the set of basic terms is infinite. This testbed comprises
1695 TRSs. All experiments were conducted on a machine that is identical to
the official competition server ($8$ AMD Opteron${}^{\text{\textregistered}}$
885 dual-core processors with 2.8GHz, $8\text{x}8$ GB memory). As timeout we
use 60 seconds. The complete experimental data can be found at http://cl-
informatik.uibk.ac.at/software/tct/experiments, where also the testbed
employed is detailed.

Table 1 summarises the experimental results of the here presented techniques
for full runtime complexity analysis in a restricted setting. The tests are
based on the use of one- and two-dimensional RMIs with coefficients over
$\\{0,1,\ldots,7\\}$ as direct technique (compare Theorem 3.9) as well as in
combination with the WDP method (compare Corollaries 5.13 and 6.14) and the
WDG method (compare Corollary 7.15). Weak dependency graphs are estimated by
the $\mathsf{TCAP}$-based technique ([20]). The tests indicate the power of
the transformation techniques introduced. Note that for linear and quadratic
runtime complexity the latter techniques are more powerful than the direct
approach. Furthermore note that the WDG method provides overall better bounds
than the WDP method.

| full
---|---
result | direct (1) | direct (2) | WDP (1) | WDP (2) | WDG (1) | WDG (2)
$\mathsf{O}(1)$ | 16 | 18 | 0 | 0 | 10 | 10
$\mathsf{O}(n)$ | 106 | 113 | 123 | 70 | 130 | 67
$\mathsf{O}(n^{2})$ | 106 | 148 | 123 | 157 | 130 | 158
timeout (60s) | 20 | 88 | 55 | 127 | 103 | 261
Table 1: Experiment results I (one- and two-dimensional RMIs separated)

However if we consider RMIs upto dimension 3 the picture becomes less clear,
cf. Table 2. Again we compare the direct approach, the WDP and WDG method and
restrict to coefficients over $\\{0,1,\ldots,7\\}$. Consider for example the
test results for cubic runtime complexity with respect to full rewriting.
While the transformation techniques are still more powerful than the direct
approach, the difference is less significant than in Table 1. On one hand this
is due to the fact that RMIs employing matrices of dimension $k$ may have a
degree strictly smaller than $k$, compare Theorem 3.9 and on the other hand
note the increase in timeouts for the more advanced techniques.

Moreover note the seemingly strange behaviour of the WDG method for innermost
rewriting: already for quadratic runtime the WDP method performs better, if we
only consider the number of yes-instances. This seems to contradict the fact
that the WDG method is in theory more powerful than the WDP method. However,
the explanation is simple: first the sets of yes-instances are incomparable
and second the more advanced technique requires more computation power. If we
would use (much) longer timeout the set of yes-instances for WDP would become
a _proper_ subset of the set of yes-instances for WDG. For example the WDG
method can prove cubic runtime complexity of the TRS AProVE_04/Liveness 6.2
from the TPDB, while the WDP method fails to give its bound.

| full | innermost
---|---|---
result | direct | WDP | WDG | direct | WDP | WDG
$\mathsf{O}(1)$ | 18 | 0 | 10 | 20 | 0 | 10
$\mathsf{O}(n)$ | 135 | 141 | 140 | 135 | 142 | 145
$\mathsf{O}(n^{2})$ | 161 | 163 | 162 | 173 | 181 | 172
$\mathsf{O}(n^{3})$ | 163 | 167 | 169 | 179 | 185 | 178
timeout (60s) | 310 | 459 | 715 | 311 | 458 | 718
Table 2: Experiment results II ($1\text{--}3$-dimensional RMIs combined)

In order to assess the advances of this paper in contrast to the conference
versions (see [4, 7]), we present in Table 3 a comparison between RMIs
with/without the use of usable arguments and a comparison of the WDP or WDG
method with/without the use of the extended weight gap principle. Again we
restrict our attention to full rewriting, as the case for innermost rewriting
provides a similar picture (see http://cl-
informatik.uibk.ac.at/software/tct/experiments for the full data).

| full
---|---
result | direct ($-$) | direct ($+$) | WDP ($-$) | WDP ($+$) | WDG ($-$) | WDG ($+$)
$\mathsf{O}(1)$ | 4 | 18 | 5 | 0 | 10 | 10
$\mathsf{O}(n)$ | 105 | 135 | 102 | 141 | 105 | 140
$\mathsf{O}(n^{2})$ | 127 | 161 | 118 | 163 | 119 | 162
$\mathsf{O}(n^{3})$ | 130 | 163 | 120 | 167 | 122 | 169
timeout (60s) | 306 | 310 | 505 | 459 | 655 | 715
Table 3: Experiment results III ($1\text{--}3$-dimensional RMIs combined)

Finally, in Table 4 we present the overall power obtained for the automated
runtime complexity analysis. Here we test the version of TCT that run for
the international annual termination competition
(TERMCOMP)777http://termcomp.uibk.ac.at/termcomp/. in 2010 in comparison to
the most recent version of TCT incorporating all techniques developed in
this paper. In addition we compare with a recent version of CaT.888http://cl-
informatik.uibk.ac.at/software/cat/.

| full | innermost
---|---|---
result |  TCT (old) |  TCT (new) | CaT |  TCT (old) |  TCT (new) | CaT
$\mathsf{O}(1)$ | 10 | 3 | 0 | 10 | 3 | 0
$\mathsf{O}(n)$ | 393 | 486 | 439 | 401 | 488 | 439
$\mathsf{O}(n^{2})$ | 394 | 493 | 452 | 403 | 502 | 452
$\mathsf{O}(n^{3})$ | 397 | 495 | 453 | 407 | 505 | 453
$\mathsf{O}(n^{4})$ | 397 | 495 | 454 | 407 | 505 | 454
Table 4: Experiment results IV ($1\text{--}3$-dimensional RMIs combined)

The results in Table 4 clearly show the increase in power in TCT, which is
due to the fact that the techniques developed in this paper have been
incorporated.

##  9 Conclusion

In this article we are concerned with automated complexity analysis of TRSs.
More precisely, we establish new and powerful results that allow the
assessment of polynomial runtime complexity of TRSs fully automatically. We
established the following results: Adapting techniques from context-sensitive
rewriting, we introduced _usable replacement maps_ that allow to increase the
applicability of direct methods. Furthermore we established the _weak
dependency pair method_ as a suitable analog of the dependency pair method in
the context of (runtime) complexity analysis. Refinements of this method have
been presented by the use of the _weight gap principle_ and _weak dependency
graphs_. In the experiments of Section 8 we assessed the viability of these
techniques. It is perhaps worthy of note to mention that our motivating
examples (Examples 3.2, 5.15, and 7.5) could not be handled by any known
technique prior to our results.

To conclude, we briefly mention related work. Based on earlier work by Arai
and the second author (see [26]) Avanzini and the second author introduced
$\text{POP}^{\ast}$ a restriction of the recursive path order (RPO) that
induces polynomial innermost runtime complexity (see [27, 15]). With respect
to derivational complexity, Zankl and Korp generalised a simple variant of our
weight gap principle to achieve a modular derivational complexity analysis
(see [28, 29]). Neurauter et al. refined in [16] matrix interpretations in the
context of derivational complexity derivational complexity (see also [30]).
Furthermore, Waldmann studied in [17] the use of weighted automata in this
setting. Based on [4, 7] Noschinski et al. incorporated a variant of weak
dependency pairs (not yet published) into the termination prover
AProVE.999This novel version of AProVE (see http://aprove.informatik.rwth-
aachen.de/) for (innermost) runtime complexity took part in TERMCOMP in 2010.
Currently this method is restricted to innermost runtime complexity, but
allows for a complexity analysis in the spirit of the dependency pair
framework. Preliminary evidence suggests that this technique is orthogonal to
the methods presented here. While all mentioned results are concerned with
_polynomial_ upper bounds on the derivational or runtime complexity of a
rewrite system, Schnabl and the second author provided in [31, 23, 32] an
analysis of the dependency pair method and its framework from a complexity
point of view. The upshot of this work is that the dependency pair framework
may induce multiple recursive derivational complexity, even if only simple
processors are considered.

Investigations into the complexity of TRSs are strongly influenced by research
in the field of ICC, which contributed the use of restricted forms of
polynomial interpretations to estimate the complexity, cf. [18]. Related
results have also been provided in the study of term rewriting
characterisations of complexity classes (compare [33]). Inspired by Bellantoni
and Cook’s recursion theoretic characterisation of the class of all polynomial
time computable functions in [34], Marion [35] defined LMPO, a variant of RPO
whose compatibility with a TRS implies that the functions computed by the TRS
is polytime computable (compare [3]). A remarkable milestone on this line is
the quasi-interpretation method by Bonfante et al. [36]. The method makes use
of standard termination methods in conjunction with special polynomial
interpretation to characterise the class of polytime computable functions. In
conjunction with _sup-interpretations_ this method is even capable of making
use of _standard_ dependency pairs (see [37]).

In principle we cannot directly compare our result on _polynomial_ runtime
complexity of TRSs with the results provided in the setting of ICC: the notion
of complexity studied is different. However, due to a recent result by
Avanzini and the second author (see [38], but compare also [39, 40]) we know
that the runtime complexity of a TRS is an _invariant_ cost model. Whenever we
have polynomial runtime complexity of a TRS $\mathcal{R}$, the functions
computed by this $\mathcal{R}$ can be implemented on a Turing machine that
runs in polynomial time. In this context, our results provide automated
techniques that can be (almost directly) employed in the context of ICC. The
qualification only refers to the fact that our results are presented for an
abstract form of programs, viz. rewrite systems.

## References

  * [1] C. Choppy, S. Kaplan, M. Soria, Complexity analysis of term-rewriting systems, Theor. Comput. Sci. 67 (2–3) (1989) 261–282.
  * [2] D. Hofbauer, C. Lautemann, Termination proofs and the length of derivations, in: Proc. 3rd International Conference on Rewriting Techniques and Applications, no. 355 in LNCS, Springer Verlag, 1989, pp. 167–177.
  * [3] E.-A. Cichon, P. Lescanne, Polynomial interpretations and the complexity of algorithms, in: Proc. 11th International Conference on Automated Deduction, Vol. 607 of LNCS, 1992, pp. 139–147.
  * [4] N. Hirokawa, G. Moser, Automated complexity analysis based on the dependency pair method, in: Proc. 4th International Joint Conference on Automated Reasoning, no. 5195 in LNAI, Springer Verlag, 2008, pp. 364–380.
  * [5] P. Baillot, J.-Y. Marion, S. R. D. Rocca, Guest editorial: Special issue on implicit computational complexity, ACM Trans. Comput. Log. 10 (4).
  * [6] T. Arts, J. Giesl, Termination of term rewriting using dependency pairs, Theor. Comput. Sci. 236 (2000) 133–178.
  * [7] N. Hirokawa, G. Moser, Complexity, graphs, and the dependency pair method, in: Proc. 15th International Conference on Logic for Programming Artificial Intelligence and Reasoning, no. 5330 in LNCS, Springer Verlag, 2008, pp. 652–666.
  * [8] F. Baader, T. Nipkow, Term Rewriting and All That, Cambridge University Press, 1998.
  * [9] TeReSe, Term Rewriting Systems, Vol. 55 of Cambridge Tracks in Theoretical Computer Science, Cambridge University Press, 2003.
  * [10] A. Geser, Relative termination, Ph.D. thesis, Universität Passau (1990).
  * [11] R. Thiemann, The DP framework for proving termination of term rewriting, Ph.D. thesis, University of Aachen, Department of Computer Science (2007).
  * [12] J. Endrullis, J. Waldmann, H. Zantema, Matrix interpretations for proving termination of term rewriting, J. Automated Reasoning 40 (3) (2008) 195–220.
  * [13] D. Hofbauer, J. Waldmann, Termination of string rewriting with matrix interpretations, in: Proc. 17th International Conference on Rewriting Techniques and Applications, Vol. 4098 of LNCS, 2006, pp. 328–342.
  * [14] T. Arts, J. Giesl, A collection of examples for termination of term rewriting using dependency pairs, Tech. Rep. AIB-2001-09, RWTH Aachen (2001).
  * [15] M. Avanzini, G. Moser, Dependency pairs and polynomial path orders, in: Proc. 20th International Conference on Rewriting Techniques and Applications, Vol. 5595 of LNCS, 2009, pp. 48–62.
  * [16] F. Neurauter, H. Zankl, A. Middeldorp, Revisiting matrix interpretations for polynomial derivational complexity of term rewriting, in: Proc. 17th International Conference on Logic for Programming Artificial Intelligence and Reasoning, Vol. 6397 of LNCS (ARCoSS), 2010, pp. 550–564.
  * [17] J. Waldmann, Polynomially bounded matrix interpretations, in: Proc. 21st International Conference on Rewriting Techniques and Applications, Vol. 6 of LIPIcs, 2010, pp. 357–372.
  * [18] G. Bonfante, A. Cichon, J.-Y. Marion, H. Touzet, Algorithms with polynomial interpretation termination proof, J. Funct. Program. 11 (1) (2001) 33–53.
  * [19] M. L. Fernández, Relaxing monotonicity for innermost termination, Inform. Proc. Lett. 93 (1) (2005) 117–123.
  * [20] J. Giesl, R. Thiemann, P. Schneider-Kamp, Proving and disproving termination of higher-order functions, in: Proc. 5th International Workshop on Frontiers of Combining Systems, 5th International Workshop, Vol. 3717 of LNAI, 2005, pp. 216–231.
  * [21] J. Giesl, R. Thiemann, P. Schneider-Kamp, S. Falke, Mechanizing and improving dependency pairs, J. Automated Reasoning 37 (3) (2006) 155–203.
  * [22] N. Hirokawa, A. Middeldorp, Tyrolean termination tool: Techniques and features, Inform. and Comput. 205 (2007) 474–511.
  * [23] G. Moser, A. Schnabl, The derivational complexity induced by the dependency pair method, Logical Methods in Computer ScienceAccepted for publication.
  * [24] J. Giesl, T. Arts, E. Ohlebusch, Modular termination proofs for rewriting using dependency pairs, J. Symbolic Comput. 34 (2002) 21–58.
  * [25] N. Hirokawa, A. Middeldorp, Automating the dependency pair method, Inform. and Comput. 199 (1,2) (2005) 172–199.
  * [26] T. Arai, G. Moser, Proofs of termination of rewrite systems for polytime functions, in: Proc. 25th Conference on Foundations of Software Technology and Theoretical Computer Science, no. 3821 in LNCS, Springer Verlag, 2005, pp. 529–540.
  * [27] M. Avanzini, G. Moser, Complexity analysis by rewriting, in: Proc. 9th International Symposium on Functional and Logic Programming, no. 4989 in LNCS, Springer Verlag, 2008, pp. 130–146.
  * [28] H. Zankl, M. Korp, Modular complexity analysis via relative complexity, in: Proc. 21st International Conference on Rewriting Techniques and Applications, Vol. 6 of LIPIcs, 2010, pp. 385–400.
  * [29] H. Zankl, M. Korp, Modular complexity analysis via relative complexity, Logical Methods in Computer ScienceSubmitted.
  * [30] G. Moser, A. Schnabl, J. Waldmann, Complexity analysis of term rewriting based on matrix and context dependent interpretations, in: Proc. 28th Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs, 2008, pp. 304–315.
  * [31] G. Moser, A. Schnabl, The derivational complexity induced by the dependency pair method, in: Proc. 20th International Conference on Rewriting Techniques and Applications, Vol. 5595 of LNCS, 2009, pp. 255–269.
  * [32] G. Moser, A. Schnabl, Termination proofs in the dependency pair framework may induce multiply recursive derivational complexities, in: Proc. 22nd International Conference on Rewriting Techniques and Applications, Vol. 10 of LIPIcs, 2011, pp. 235–250.
  * [33] E.-A. Cichon, A. Weiermann, Term rewriting theory for the primitive recursive functions., Ann. Pure Appl. Logic 83 (3) (1997) 199–223.
  * [34] S. Bellantoni, S. Cook, A new recursion-theoretic characterization of the polytime functions, Comput. Complexity 2 (2) (1992) 97–110.
  * [35] J.-Y. Marion, Analysing the implicit complexity of programs, Inform. and Comput. 183 (2003) 2–18.
  * [36] G. Bonfante, J.-Y. Marion, J.-Y. Moyen, Quasi-interpretations: A way to control resources, Theor. Comput. Sci.To appear.
  * [37] J.-Y. Marion, R. Péchoux, Sup-interpretations, a semantic method for static analysis of program resources, ACM Trans. Comput. Log. 10 (4).
  * [38] M. Avanzini, G. Moser, Closing the gap between runtime complexity and polytime computability, in: Proc. 21st International Conference on Rewriting Techniques and Applications, Vol. 6 of LIPIcs, 2010, pp. 33–48.
  * [39] U. Dal Lago, S. Martini, On constructor rewrite systems and the lambda-calculus, in: Proc. 36th ICALP, Vol. 5556 of LNCS, Springer Verlag, 2009, pp. 163–174.
  * [40] U. Dal Lago, S. Martini, Derivational Complexity is an Invariant Cost Model, in: Proc. 1st FOPARA, 2009.