# Improving Out-of-Distribution Generalization of Trajectory Prediction
for Autonomous Driving via Polynomial Representations

Yue Yao1,2, Shengchao Yan3, Daniel Goehring2, Wolfram Burgard4, Joerg
Reichardt1 The authors are with 1Continental AG, 2Freie Universität Berlin,
3Department of Computer Science, University of Freiburg, 4Department of
Engineering, University of Technology Nuremberg.

###### Abstract

Robustness against Out-of-Distribution (OoD) samples is a key performance
indicator of a trajectory prediction model. However, the development and
ranking of state-of-the-art (SotA) models are driven by their In-Distribution
(ID) performance on individual competition datasets. We present an OoD testing
protocol that homogenizes datasets and prediction tasks across two large-scale
motion datasets. We introduce a novel prediction algorithm based on polynomial
representations for agent trajectory and road geometry on both the input and
output sides of the model. With a much smaller model size, training effort,
and inference time, we reach near SotA performance for ID testing and
significantly improve robustness in OoD testing. Within our OoD testing
protocol, we further study two augmentation strategies of SotA models and
their effects on model generalization. Highlighting the contrast between ID
and OoD performance, we suggest adding OoD testing to the evaluation criteria
of trajectory prediction models.

##  I Introduction

Figure 1: Our proposed model architecture. Agent histories and road geometry
are both represented via polynomials. The tracked initial states and predicted
states are fused into one polynomial trajectory prediction, ensuring
continuity of past observation and future prediction.

Trajectory prediction is essential for autonomous driving, with robustness
being a key factor for practical applications. The development of trajectory
prediction models is catalyzed through public datasets and associated
competitions, such as Argoverse 1 (A1) [1], Argoverse 2 (A2) [2], Waymo Motion
(WO) [3]. These competitions provide a set of standardized metrics and test
protocol that scores prediction systems on test data withheld from all
competitors. This is intended to ensure two things: objective comparability of
results and generalization ability due to the held-out test set.

Among the top-performing models based on deep learning, we observe a trend to
ever more parameter-rich and expressive models [4, 5, 6] \- trained
specifically with the data of each competition. This begs the question of
whether the stellar performance of these models is due to their ability to
adapt to each dataset specifically, i.e., over-fit. Prediction competitions
try to guard against over-fitting by scoring models with test samples that are
withheld from competitors. However, these test examples still share
similarities with the training samples, such as the sensor setup, map
representation, post-processing, geographic, and scenario selection biases
employed in dataset creation. Consequently, the test scores reported in each
competition are examples of _In-Distribution_ (ID) testing.

For practical application, the performance of trajectory prediction should be
independent of these shared biases in a single dataset and measured by _Out-
of-Distribution_ (OoD) testing, e.g., across different datasets. However, the
efforts for cross-dataset evaluation are hampered by the in-homogeneous data
format and task details among datasets and competitions. Notable distinctions
are the different lengths of scenario, observation history, and prediction
horizon in each dataset.

Therefore, in this work, we attempt to homogenize the data formats and
prediction tasks to enable OoD testing across two large-scale motion datasets:
A2 and WO. Based on our OoD testing, we further explore the possibilities to
enhance model robustness against OoD samples.

One strategy to improve the robustness of any deep learning model is to
increase the amount of training data. Bahari et al. [7] have shown that
generalization performance can be improved by augmenting training data with
programmatically created variations. While such an approach does increase
generalization ability, it further increases training effort and cannot
guarantee generalization. Further, ensuring that a data augmentation strategy
covers all possible variations is not easy.

We follow a complementary strategy and instead of providing more training
data, limit the expressiveness of our model by constraining its input and
output representation. This comes with the added benefit of a much smaller
model size, reduced training effort and faster inference times. At the same
time, we retain near state-of-the-art (SotA) prediction performance for ID
test cases and show significantly improved robustness in OoD testing. Our key
contributions are as follows:

  * •

We provide a dataset homogenization protocol that enables Out-of-Distribution
(OoD) testing of prediction algorithms across different large-scale motion
datasets.

  * •

We study the OoD robustness of two SotA models and explore the effect of their
augmentation strategies on In-Distribution (ID) and OoD test results.

  * •

We propose an efficient multi-modal predictor baseline with competitive ID
performance and superior OoD robustness by representing trajectories and map
features parametrically as polynomials.

Our paper is organized as follows: We first review the recent trajectory
prediction models and their design decisions with respect to data
representation and augmentation strategy. Out of the body of related work, we
select two benchmark models, Forecast-MAE (FMAE) [8] and QCNet [6], and detail
how dataset and competition characteristics have shaped their model designs.
Next, we propose our dataset homogenization protocol for OoD testing. In
contrast to the benchmark design, we introduce our approach by incorporating
constrained parametric representations - polynomials for both inputs and
outputs. We then report ID and OoD testing results for all three models plus a
number of variants. Our results highlight the impact of different augmentation
strategies in ID and OoD testing and the increase in OoD robustness due to our
choice of polynomial representations. Finally, we argue for adopting OoD
testing as a performance measure of equal value to ID testing.

We open-source our code online [9]. The camera-ready version of this paper
will be published in the proceedings of IROS 2024.

##  II Related Work and Benchmark Models

###  II-A Data Representation

The formats of individual datasets and competition rules greatly influence the
design decisions of the models proposed in the literature. Models based on
deep learning typically opt for a direct ingestion of the data as given.
Recent studies employ _sequence-based representation_ , e.g., sequences of
data points, as the model’s input and output [8, 6, 10, 11]. This
representation aligns the format of measurements in datasets and efficiently
captures various information, e.g., agent trajectories and road geometries.
The downside of this representation is the high redundancy and variance. The
presence of measurement noise and outliers in datasets may lead to physically
infeasible predictions. Additionally, the computational requirement of this
approach scales with the length and temporal/spatial resolution of
trajectories and road geometries.

Some previous works explored the possibility of using _polynomial
representations_ for predictions [12, 13]. Su et al. [13] highlight the
temporal continuity, i.e., the ability to provide arbitrary temporal
resolution, of this representation. Reichardt [14] argues for using polynomial
representations to integrate trajectory tracking and prediction into a
filtering problem. Polynomial representations restrict the kind of
trajectories that can be represented and introduce bias into prediction
systems. This limited flexibility is generally associated with greater
computational efficiency, smaller model capacity and hence better
generalization. However, representing the _inputs_ with polynomials has not
been extensively researched and deployed in recent works. In a recent study,
we showed that polynomials of moderate degree can represent real-world
trajectories with a high degree of accuracy [15]. This result motivates the
use of polynomial representations in our architecture.

###  II-B Data Augmentation

Competitions typically designate one or more agents in a scenario as _focal_
agent and only score predictions for focal agents. However, training the model
exclusively with the focal agent’s behavior fails to exploit all available
data. To address this, predicting the future motion of non-focal agents is a
typical augmentation strategy for training. As there are many more non-focal
agents than focal agents, another important design decision relates to how
authors interpret the importance of focal vs. non-focal agent data.

We select two open-sourced and thoroughly documented SotA models: Forecast-MAE
[8] (FMAE) and QCNet [6], with nearly 1900k and 7600k parameters,
respectively. As summarized in Table I, both models employ sequence-based
representation but exhibit different strategies in dealing with non-focal
agents:

  * Heterogeneous Augmentation: FMAE follows the prediction competition protocol and prioritizes focal agent prediction. Thus, agent history and map information are computed within the _focal agent_ coordinate frame. Compared to the _multi-modal_ prediction of the focal agent, FMAE only outputs _uni-modal_ prediction for non-focal agents. The prediction error of the focal agent also weighs higher in loss function than non-focal agents.

  * Homogeneous Augmentation: QCNet does not focus on the selected focal agent and proposes a more generalized approach. It encodes the information of agents and map elements in each agent’s _individual_ coordinate frame. It outputs _multi-modal_ predictions for focal and non-focal agents alike, ensuring a consistent prediction task for all agents. The loss of focal agent prediction shares the same weight as non-focal agents.

Figure 2 illustrates the augmentation strategies of our benchmark models FMAE
and QCNet.

Figure 2: The two augmentation strategies for non-focal agent data employed in
benchmark models. Left: FMAE employs heterogeneous augmentation, representing
information in the focal agent’s coordinate frame and only making uni-modal
predictions for non-focal agents. Right: QCNet employs homogeneous
augmentation, encoding information in each agent’s individual coordinate frame
and making multi-modal predictions for both focal and non-focal agents alike.

To study the influence of these augmentation approaches independently of data
representation, we add a third augmentation strategy for comparison: no
augmentation. This can simply be achieved by removing the loss of non-focal
agents in each model, thus limiting the model to learn from focal agent
behavior only. We denote the benchmark models without augmentation as ”FMAE-
noAug” and ”QCNet-noAug”.

For our own model, we will implement all three modes of augmentation for
comparison.

augmentation |  input and output representation
---|---
strategy |  sequence-based |  polynomial-based (ours)
heterogeneous |  FMAE [8] |  EP-F
homogeneous |  QCNet [6] |  EP-Q
w/o augmentation |  FMAE-noAug |  EP-noAug
QCNet-noAug |
|  |
TABLE I: Model variants under study based on augmentation strategies and data
representations.

##  III OoD testing and Dataset Homogenization

The irrelevant data creation processes and platforms across motion datasets
present us with the opportunity to perform OoD testing on truly independent
data samples. However, this also comes with the challenges of working around
inconsistencies in data formats and prediction tasks between datasets.

|  Argoverse 2 (A2) Dataset [2] |  Waymo Open Dataset (WO) [3] |  Homogenized Dataset
---|---|---|---
|  |  train test
#samples (train / val / test) |  $199\,908$ / $24\,988$ / $24\,984$ |  $487\,002$ / $44\,097$ / $44\,920$ |  -
#cities |  6 |  6 |  -
scenario length |  11s |  9.1s |  -
sampling rate |  10 Hz |  10 Hz |  -
history length |  5s |  1.1s |  5s
prediction horizon |  6s |  8s |  6s 4.1s
map information | lane center |  yes |  yes |  yes
lane boundary |  yes |  not for junction lanes |  no
junction lanes labeled |  yes |  no |  no
prediction target | # focal agents |  1 |  up to 8 |  1
ego included |  no |  yes |  no
fully observed |  yes |  not guaranteed |  yes
|  |  |  |
TABLE II: Datasets comparison and homogenization protocol for OoD testing.

We propose our OoD testing protocol by training and testing models on two
different large-scale datasets: A2 and WO. We summarise the characteristics of
both datasets in Table II. Algorithmic improvements in generalization ability
are more easily identified when training on the smaller of two datasets and
testing on the larger ones. Consequently, we train on the training set from
A2, comprising $199\,908$ samples. As the test set of the A2 and WO
competitions are not accessible, they cannot be included in our homogenization
protocol. Thus, for ID testing, we settle for the validation split of A2, and
for OoD testing use the validation split of WO. The difference between ID and
OoD results demonstrates a model’s robustness against OoD test cases.

There are multiple notable distinctions between A2 and WO. One obvious
distinction is the different scenario lengths: a scenario in A2 is $11$
seconds long and consists of $5$ seconds of observation history and $6$
seconds of future to predict. WO only provides $1.1$ seconds of observation
history but requires an $8$-second prediction horizon. Moreover, A2 designates
and scores only one _focal agent_ per scenario, whereas there are up to 8 such
_focal agents_ in WO. The focal agent in A2 is never the ego vehicle and
remains fully observed throughout the prediction horizon, which is not
guaranteed in WO.

To facilitate the OoD testing, we homogenize the datasets and adopt the
following settings for both datasets and summarize them in Table II:

  * •

History Length: We set the history length to 5 seconds (50 steps) as in A2.

  * •

Prediction Horizon: We maintain the 6-second prediction horizon for training
but only evaluated the first 4.1s of prediction due to the limited recording
length in WO.

  * •

Map Information: We exclude boundary information and the label of junction
lanes due to the information’s absence in WO. Only lane segments and
crosswalks are considered map elements in homogenized data due to their
availability in both datasets.

  * •

Focal Agent: We take the same focal agent as labeled in A2. From WO, only the
first fully observed, non-ego agent in the list of focal agents is chosen. As
the list of focal agents is unordered, this corresponds to randomly sampling a
single fully observed focal agent.

Fulfilling the focal agent’s selection criterion above, we have $24\,988$ and
$42\,465$ valid samples from A2 and WO validation sets for ID and OoD testing,
respectively.

##  IV Proposed Model and Data Representation

The key innovation of our model is its choice of representation for map
elements and trajectories on both input and output sides of the model. Here,
we propose to use a parametric representation in terms of polynomials. This
constrains the model’s expressiveness compared to sequence-based data
representations. Such a parametric representation is easily pre-computed for
map elements and algorithms for online tracking and filtering agent
observations into trajectories already exist [14].

Our prior work on trajectory representation [15] has shown that polynomials
are an accurate representation of agent trajectories and should not present a
limiting factor to the achievable prediction performance. Independent research
suggests that sequence-based data representations may carry high-frequency
information, which can result in over-fitting [16].

With the polynomial inputs and outputs as our key innovation, we present our
approach with great model efficiency and generalization: _Everything
Polynomial_ (EP). We now elaborate our approach to represent data with
polynomials.

###  IV-A Inputs as Polynomials

We employ Bernstein polynomials to represent the agent history and map
geometry. The parameters of Bernstein polynomials have spatial semantics as
_control points_.

_Agent History_ : Based on the Akaike Information Criterion (AIC) [17]
presented in [15], the 5-second history trajectories of vehicles, cyclists,
and pedestrians in A2 and WO are represented optimally with 5-degree
polynomials. We also use the 5-degree polynomial for the ego vehicle. We track
the control points of agent history with the method proposed in [14] and
incorporate the observation noise models proposed in [15].

_Map_ : Map elements, such as lane segments and crosswalks, are represented
with 3-degree polynomials - a degree consistent with OpenDRIVE [18] standards.
We fit the sample points of map elements via the total-least-squares method by
Borges-Pastva [19]. Lane segments in WO are longer than those in A2, posing a
challenge for fitting them with 3-degree polynomials. Therefore, we
iteratively split the lane segments by half until the fit error is under
$0.1$m.

We visualized one traffic scenario in A2 with polynomial representations in
Figure 3. The polynomial representation only requires $40.8\%$ and $8.7\%$ of
data space compared to the sample points provided in A2 and WO, respectively.

Figure 3: One traffic scenario in A2 represented with polynomials. model |  minADE1 |  minFDE1 |  minADE6 |  minFDE6 | # model | inference time
---|---|---|---|---|---|---
[m] |  [m] |  [m] |  [m] | params [k] | [ms]
QCNet [6] |  1.702 |  4.309 |  0.643 |  1.244 | 7600 | 120.89
(100.0%) |  (100.0%) |  (100.0%) |  (100.0%) | (100.0%) | (100.0%)
Forecast-MAE [8] |  1.741 |  4.355 |  0.709 |  1.392 | 1900 | 12.63
w pre-train |  (102.2%) |  (101.1%) |  (110.3%) |  (111.9%) | (25.0%) | (10.4%)
EP-Q (ours) |  2.134 |  5.415 |  0.841 |  1.683 | 334 | 5.72
(125.4%) |  (125.7%) |  (131.0%) |  (135.3%) | (4.4%) | (4.7%)
EP-F (ours) |  1.887 |  4.567 |  0.801 |  1.526 |  345 (4.5%) |  4.66 (3.9%)
(110.9%) |  (106.0%) |  (124.6%) |  (122.7%)
EP-F w flip (ours) |  1.846 |  4.456 |  0.786 |  1.485
(108.5%) |  (103.4%) |  (122.2%) |  (119.4%)
TABLE III: Result of In-Distribution testing (6-second prediction horizon) in
competition setting on Argoverse 2 test set. For all the metrics, lower the
better. Inference time is tested on one Tesla T4 GPU with a scenario of 50
agents and 150 map elements.

###  IV-B Outputs as Polynomials

The 6-second predicted trajectories are formulated as 6-degree polynomials,
one degree higher than indicated by AIC in [15]. Instead of predicting the
polynomial parameters of future trajectories, our model predicts several
future kinematic vehicle states. By fusing the predicted future states with
current tracked states, we recalculate the polynomial parameters and
reconstruct the future trajectory. Details are presented in Appendix A.

###  IV-C Model

The pipeline of EP is illustrated in Figure 1. EP employs the popular encoder
and decoder architecture and its implementation details are presented in
Appendix A.

Following the different augmentation strategies by our benchmark models, we
implemented three EP variants: (1) EP-F employs the heterogeneous augmentation
of FMAE. (2) EP-Q employs the homogeneous augmentation of QCNet. (3) EP-noAug
has no augmentation. Table I summarizes the design choices of the different
models under study.

Due to the compact polynomial representations for inputs and outputs, EP
variants only employ around 345k model parameters, which is only $4.5\%$ the
size of QCNet and $18.2\%$ the size of FMAE as listed in Table III.

Since we focus on OoD robustness, scaling up our model for more model capacity
and potentially better ID performance is not prioritized in this work.

##  V Experimental Results

###  V-A Experiment Setup on Homogenized Data

On the homogenized A2 training data, all models are trained from scratch with
hyperparameters reported for A2 competition performance. Due to our dataset
homogenization settings, we have to adjust the data pre-processing and
corresponding encoding layers in QCNet, e.g., removing the layers for encoding
the label of junction lanes. FMAE’s architecture is not affected by our data
homogenization. Training settings of EP variants are summarized in Appendix
A-C.

###  V-B Metrics

For ID testing, we use the official benchmark metrics, including minimum
Average Displacement Error ($minADE_{K}$) and minimum Final Displacement Error
($minFDE_{K}$), for evaluation. The metric $minADE_{K}$ calculates the
Euclidean distance in meters between the ground-truth trajectory and the best
of $K$ predicted trajectories as an average of all future time steps.
Conversely, $minFDE_{K}$ focuses solely on the prediction error at the final
time step, emphasizing long-term performance.

For OoD testing, we also propose $\Delta minADE_{K}$ and $\Delta minFDE_{K}$
as the difference of displacement error between ID and OoD testing to measure
model robustness. In accordance with standard practice, $K$ is selected as 1
and 6.

###  V-C ID Results with Competition Settings

Like the other studies, we first present the best ID test results of all
models according to the A2 prediction competition protocol in Table III.
Benchmark results are from the original authors. For EP, we also include the
results when augmenting the data by symmetrizing around the x-axis, i.e.
flipping all left turns into right turns and vice versa.

Though the performance in ID testing on the A2 test set is not the focus of
our work, our EP still achieves near state-of-the-art performance with a
significantly smaller model size. For instance, with “flip” data augmentation,
the $minFDE_{1}$ of EP-F is only $3.4\%$ higher compared to QCNet. Though EP
exhibits a considerable gap compared to QCNet in terms of multi-modal
prediction (K=6), it exhibits only less than $10$cm additional prediction
error in $minADE_{6}$ and $minFDE_{6}$ compared to FMAE with pre-train. EP has
a faster inference time, requiring only $3.9\%$ of QCNet’s and $36.9\%$ of
FMAE’s inference time, which is essential in real-time applications. Another
notable point is the better ID performance of EP-F compared to EP-Q. This
indicates that heterogeneous augmentation shows more effectiveness than
homogeneous augmentation in ID testing when only a single focal agent is
scored.

Next, we examine the impact of dataset homogenization and augmentation. In
Figure 4, we can see that the alterations due to dataset homogenization, e.g.,
excluding lane boundaries, have only little effect on model performance.
Removing the data augmentation, however, has a small but noticeable negative
effect on ID performance for both benchmark models. These results also show
that our retraining works as expected.

Figure 4: ID performance of benchmarks on A2. Dashed Lines: Results reported
by original authors with competition settings. Bars: Results for retrained
benchmark models on homogenized datasets.

###  V-D OoD Testing Results

The key question now is whether the results achieved in ID testing on A2 will
translate to OoD testing on WO. Figure 5 summarizes the results. As discussed,
the relative and absolute increase in the prediction metric will serve as our
measure of robustness and generalization ability. We will present OoD results
from three perspectives: (1) augmentation strategy, (2) data representation,
and (3) contrast results between ID and OoD testing.

####  V-D1 Augmentation Strategy

We observe that without augmentation, i.e., excluding the non-focal agents in
the loss function, all models generalize poorly on all metrics, but our model
has the smallest relative and absolute increase in error in all cases.

Though heterogeneous augmentation does marginally reduce FMAE’s prediction
error for both ID and OoD testing, the relative and absolute increase in
prediction error between ID and OoD samples is practically the same as in the
non-augmented case, e.g., $+27.9$cm $(61.5\%)$ vs. $+29.5$cm $(69.7\%)$ in
$\Delta minADE_{6}$.

Figure 5: The OoD testing results of FMAE, QCNet, EP and their variants. We
indicate the _absolute_ and _relative_ difference in displacement error
between ID and OoD results. Solid: The ID results by training on the
homogenized A2 training set and testing on the homogenized A2 validation set.
Transparent: The increased displacement error in OoD testing by training on
the homogenized A2 training set and testing on the homogenized WO validation
set.

On the other hand, the robustness of QCNet significantly benefits from the
homogeneous augmentation with reduced $\Delta minFDE_{1}$ from $+180.2$cm
$(71.5\%)$ to $+106.7$cm $(46.4\%)$. Compared to EP-noAug, EP-F and EP-Q
replicate the behavior observed from FMAE and QCNet, e.g., with only a
marginal impact from heterogeneous augmentation and a significant impact from
homogeneous augmentation.

####  V-D2 Data Representation

Our EP variants exhibit improved robustness compared to benchmarks with
sequence-based data independent of data augmentation strategy. For instance,
EP-F outperforms FMAE by demonstrating lower prediction errors and a lower
increase in prediction errors in OoD testing. Similarly, compared to QCNet,
EP-Q also demonstrates improved robustness, even achieving a reduction in
prediction error of $-2.2$cm $(-1.9\%)$ in $\Delta minADE_{1}$.

####  V-D3 ID vs OoD results

We observe multiple reversals in performance between ID and OoD testing
results: (1) Despite FMAE demonstrating comparable ID performance to QCNet, it
exhibits significantly lower robustness than QCNet in OoD testing. (2) While
FMAE and QCNet outperform EP on ID samples, EP shows lower prediction error
than FMAE and QCNet across multiple metrics in OoD testing. (3) There is a
reversal in performance between EP-F and EP-Q in both ID and OoD testing.

model |  $minADE_{1}|minFDE_{1}$ [m]
---|---
ID |  OoD
EP-F |  1.08 2.56 |  1.32 3.45
EP-F (w flip) |  1.06 2.50 |  1.35 3.53
|  |
TABLE IV: ID and OoD testing results (4.1-second prediction horizon) of EP-F
and EP-F (w flip).

Moreover, we also note the contrasting impact of ”data flipping” in ID and OoD
testing, as summarized in Table IV. This indicates that improper data
augmentation can in fact impair model generalization.

The differences between ID and OoD results underscore the importance of OoD
testing for a thorough evaluation of trajectory prediction models.

##  VI Conclusion

Recent SotA trajectory prediction models have thoroughly optimized their In-
Distribution (ID) performance and present outstanding results in test sets
evaluated in individual prediction competition. However, better ID performance
does not automatically guarantee higher Out-of-Distribution (OoD) performance.
In fact, performance differences can and do reverse in OoD settings. Our
proposed OoD testing protocol enables a fresh perspective for model evaluation
in trajectory prediction that we hope the community will adopt. With our
protocol, we demonstrate the robustness improvement from _homogenous
augmentation_ and prove the benefits of _polynomial representation_ as
employed in our EP model. With a much smaller model size and lower inference
time, EP achieves near SotA ID performance and exhibits significantly improved
OoD robustness compared to benchmark models. This work represents an initial
step toward a trajectory prediction model that is capable of generalizing to
different datasets and is robust under changes in sensor setup, scenario
selection strategy or post-processing of training data. More sophisticated
models based on this concept will be developed to improve the performance for
both In- and Out-of-Distribution evaluations. Our work analyzes two important
factors affecting model robustness: augmentation strategy and data
representation. Other factors, such as model size, are not explored and remain
to be researched.

## ACKNOWLEDGMENT

Authors would like to thank Andreas Philipp for many useful discussions and
acknowledge funding from the German Federal Ministry for Economic Affairs and
Climate Action within the project “KI Wissen – Automotive AI powered by
Knowledge”.

## References

  * [1] M.-F. Chang, J. Lambert, P. Sangkloy, J. Singh, S. Bak, A. Hartnett, D. Wang, P. Carr, S. Lucey, D. Ramanan, and J. Hays, “Argoverse: 3d tracking and forecasting with rich maps,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [2] B. Wilson, W. Qi, T. Agarwal, J. Lambert, J. Singh, S. Khandelwal, B. Pan, R. Kumar, A. Hartnett, J. K. Pontes, _et al._ , “Argoverse 2: Next generation datasets for self-driving perception and forecasting,” in _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2)_ , 2021.
  * [3] S. Ettinger, S. Cheng, B. Caine, C. Liu, H. Zhao, S. Pradhan, Y. Chai, B. Sapp, C. R. Qi, Y. Zhou, _et al._ , “Large scale interactive motion forecasting for autonomous driving: The waymo open motion dataset,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 9710–9719.
  * [4] Z. Zhou, L. Ye, J. Wang, K. Wu, and K. Lu, “Hivt: Hierarchical vector transformer for multi-agent motion prediction,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 8823–8833.
  * [5] S. Shi, L. Jiang, D. Dai, and B. Schiele, “MTR++: multi-agent motion prediction with symmetric scene modeling and guided intention querying,” _CoRR_ , vol. abs/2306.17770, 2023.
  * [6] Z. Zhou, J. Wang, Y.-H. Li, and Y.-K. Huang, “Query-centric trajectory prediction,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 17 863–17 873.
  * [7] M. Bahari, S. Saadatnejad, A. Rahimi, M. Shaverdikondori, A. H. Shahidzadeh, S.-M. Moosavi-Dezfooli, and A. Alahi, “Vehicle trajectory prediction works, but not everywhere,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 17 123–17 133.
  * [8] J. Cheng, X. Mei, and M. Liu, “Forecast-mae: Self-supervised pre-training for motion forecasting with masked autoencoders,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2023, pp. 8679–8689.
  * [9] Continental AG, “KI Wissen: towards the better model generalization in motion predition,” https://github.com/continental/kiwissen-towards-the-better-model-generalization-in-motion-prediction, 2024.
  * [10] M. Liang, B. Yang, R. Hu, Y. Chen, R. Liao, S. Feng, and R. Urtasun, “Learning lane graph representations for motion forecasting,” in _European Conference on Computer Vision_. Springer, 2020, pp. 541–556.
  * [11] B. Varadarajan, A. Hefny, A. Srivastava, K. S. Refaat, N. Nayakanti, A. Cornman, K. Chen, B. Douillard, C. P. Lam, D. Anguelov, _et al._ , “Multipath++: Efficient information fusion and trajectory aggregation for behavior prediction,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 7814–7821.
  * [12] T. Buhet, E. Wirbel, A. Bursuc, and X. Perrotton, “Plop: Probabilistic polynomial objects trajectory planning for autonomous driving,” _CoRR_ , vol. abs/2003.08744, 2020.
  * [13] Z. Su, C. Wang, H. Cui, N. Djuric, C. Vallespi-Gonzalez, and D. Bradley, “Temporally-continuous probabilistic prediction using polynomial trajectory parameterization,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2021, pp. 3837–3843.
  * [14] J. Reichardt, “Trajectories as markov-states for long term traffic scene prediction,” in _14-th UniDAS FAS-Workshop_ , 2022, p. 14.
  * [15] Y. Yao, D. Goehring, and J. Reichardt, “An empirical bayes analysis of object trajectory representation models,” in _IEEE 26th International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2023, pp. 902–909.
  * [16] D. Yin, R. Gontijo Lopes, J. Shlens, E. D. Cubuk, and J. Gilmer, “A fourier perspective on model robustness in computer vision,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [17] H. Akaike, “Information theory and an extension of the maximum likelihood principle,” in _Selected papers of hirotugu akaike_. Springer, 1998, pp. 199–213.
  * [18] Association for Standardization of Automation and Measuring Systems (ASAM), “ASAM OpenDRIVE,” https://www.asam.net/standards/detail/opendrive/, 2023, accessed: 07.03.2024.
  * [19] C. F. Borges and T. Pastva, “Total least squares fitting of bézier and b-spline curves to ordered data,” _Computer Aided Geometric Design_ , vol. 19, no. 4, pp. 275–289, 2002.
  * [20] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [21] R. Xiong, Y. Yang, D. He, K. Zheng, S. Zheng, C. Xing, H. Zhang, Y. Lan, L. Wang, and T. Liu, “On layer normalization in the transformer architecture,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 10 524–10 533.

##  Appendix A Implementation Details of Our Model

###  A-A Model

####  A-A1 Input

The control points of $A$ agents in either _focal agent_ or _individual_
coordinate are denoted as $\boldsymbol{\omega}^{a}_{n}\in\mathbb{R}^{A\times
2}$ with $n\in\\{0,1,\cdots,5\\}$. Following the popular vectorization
approach, we compute the vector between control points as
$\boldsymbol{\delta}^{a}_{n}=\boldsymbol{\omega}^{a}_{n}-\boldsymbol{\omega}^{a}_{n-1}$
for capturing the kinematic of agents. To describe the spatial relationship,
we employ the last control point $\boldsymbol{\omega}^{a}_{5}$ and the
normalized vector
$\boldsymbol{\theta}^{a}_{5}=norm(\boldsymbol{\delta}^{a}_{5})$ as the
reference position and orientation for agents. The time window of agent
appearance is denoted as $\boldsymbol{TW}\in\mathbb{R}^{A\times 2}$.
Therefore, the features of agents include
$\boldsymbol{\Delta}^{a}=[\boldsymbol{\delta}^{a}_{1},\boldsymbol{\delta}^{a}_{2},\cdots,\boldsymbol{\delta}^{a}_{5}]$,
$\boldsymbol{PI}^{a}=[\boldsymbol{\omega}^{a}_{5},cos(\boldsymbol{\theta}^{a}_{5}),sin(\boldsymbol{\theta}^{a}_{5})]$
and $\boldsymbol{TW}$. The features of $M$ map elements are computed similarly
with considering the initial point as the reference, denoting as
$\boldsymbol{\Delta}^{m}=[\boldsymbol{\delta}^{m}_{1},\boldsymbol{\delta}^{m}_{2},\boldsymbol{\delta}^{m}_{3}]$
and
$\boldsymbol{PI}^{m}=[\boldsymbol{\omega}^{m}_{0},cos(\boldsymbol{\theta}^{m}_{1}),sin(\boldsymbol{\theta}^{m}_{1})]$.

Figure 6: Encoder architecture of EP variants.

####  A-A2 Encoder

As visualized in Figure 6, we employ simple 3-layer MLPs to encode the
features of agents and map elements. Semantic attributes, such as agent type
and lane type, are encoded with individual embedding layers. Embedded features
are added and fused to agent tokens $\boldsymbol{T}^{a}\in\mathbb{R}^{A\times
D}$ and map element tokens $\boldsymbol{T}^{m}\in\mathbb{R}^{M\times D}$,
where $D$ denotes the hidden dimension. Multiple attention blocks based on
Transformer [20] and ”pre-layer normalization” [21] perform the _map element_
-_map element_ , _agent_ -_map element_ and _agent_ -_agent_ attentions
sequentially and update $\boldsymbol{T}^{a}$. All EP variants share the same
encoder architecture.

Figure 7: Decoder architectures of EP-F, EP-Q and EP-noAug.

####  A-A3 Decoder

In Figure 7, we visualize the two decoder architectures of EP-F (EP-noAug) and
EP-Q due to different augmentation strategies.

The embedded agent features can be decoded in two ways: (1) For multi-modal
prediction, the agent token $\boldsymbol{T}^{a}$ is firstly projected to
multiple modes and substantially decoded to predicted states
$\boldsymbol{s}^{pred}$ and probabilities $\boldsymbol{p}$ for each mode. (2)
For uni-modal prediction, the agent token $\boldsymbol{T}^{a}$ is directly
decoded to the predicted states of a single mode.

Consider the $k$-th mode of $i$-th agent, we concatenate the two-dimensional
states as the vector
$\boldsymbol{s}_{i,k}=[\boldsymbol{p}^{track}_{i,0},\boldsymbol{p}^{pred}_{i,k,30},\boldsymbol{v}^{pred}_{i,k,30},\boldsymbol{a}^{pred}_{i,k,30},\boldsymbol{p}^{pred}_{i,k,60},\boldsymbol{v}^{pred}_{i,k,60},{a}^{pred}_{i,k,60}],\boldsymbol{s}_{i,k}\in\mathbb{R}^{14}$,
where $\boldsymbol{p}^{track}_{i,0}$ denotes the tracked position at current
time step,
$\boldsymbol{p}^{pred}_{i,k,30},\boldsymbol{v}^{pred}_{i,k,30},\boldsymbol{a}^{pred}_{i,k,30}$
are the predicted position, velocity and acceleration at 3s (30 steps) in the
future, respectively.
$\boldsymbol{p}^{pred}_{i,k,60},\boldsymbol{v}^{pred}_{i,k,60},{a}^{pred}_{i,k,60}$
are the predicted position, velocity and acceleration at 6s (60 steps) in the
future, respectively.

We follow the same notation as in [15] and form the monomial basis functions
as a vector $\boldsymbol{\phi}(t_{m})\in\mathbb{R}^{7}$ by concatenation
$\boldsymbol{\phi}(t_{m})=[\phi_{0}(t_{m}),\cdots,\phi_{6}(t_{m})]^{\top}$,
where $t_{m}$ denotes the timestamp at $m$-th step in the future. The
derivatives of the monomial basis function $\boldsymbol{\dot{\phi}}(t{m})$ and
$\boldsymbol{\ddot{\phi}}(t_{m})$ can be acquired by incorporating the linear
derivative operator $\boldsymbol{D}\in\mathbb{R}^{7\times 7}$ mentioned in
[14]. We construct the $14\times 14$ observation matrix
$\boldsymbol{H}=[\boldsymbol{\phi}(t_{0}),\boldsymbol{\phi}(t_{30}),\dot{\boldsymbol{\phi}}(t_{30}),\ddot{\boldsymbol{\phi}}(t_{30}),\boldsymbol{\phi}(t_{60}),\dot{\boldsymbol{\phi}}(t_{60}),\ddot{\boldsymbol{\phi}}(t_{60})]^{\top}\otimes\mathbf{I}_{2}$,
where $\mathbf{I}_{2}$ is a $2\times 2$ identity matrix and $\otimes$ denotes
the Kronecker product. The trajectory parameters $\boldsymbol{\omega}_{i,k}$
of the $k$-th predicted mode are expressed as
$\boldsymbol{\omega}^{pred}_{i,k}=(\boldsymbol{H}^{\top}\boldsymbol{H})^{-1}\boldsymbol{H}^{\top}\boldsymbol{s}_{i,k}$.

###  A-B Training Loss

We employ $minADE_{6}$ as regression loss $l^{reg,multi}$ and weighted average
displacement error, with the weight of predicted probability $\boldsymbol{p}$,
as classification loss $l^{cls,multi}$ for multi-modal prediction. We
calculate average displacement error as regression loss for uni-modal
prediction $l^{reg,uni}$. Thus, the training losses of EP variants are
expressed as:

$\displaystyle l_{EP-F}=$ $\displaystyle
l^{reg,multi}_{focal}+l^{cls,multi}_{focal}+l^{reg,uni}_{non\\_focal}$ (1)
$\displaystyle l_{EP-Q}=$ $\displaystyle
l^{reg,multi}_{all}+l^{cls,multi}_{all}$ $\displaystyle l_{EP-noAug}=$
$\displaystyle l^{reg,multi}_{focal}+l^{cls,multi}_{focal}$

where sub-indices ”focal,” ”non-focal,” and ”all” refer to the focal agent,
non-focal agents, and all agents, respectively.

###  A-C Experiment Settings

We report the settings of EP variants in Table V. Note that the batch size and
number of epochs are designed to ensure the same training iterations for all
EP variants.

model |  EP-F & EP-noAug |  EP-Q
---|---|---
hidden dimension $D$ | 64
optimizer | Adam
learning rate |  1e-3 |  5e-4
learning rate schedule | cosine
batch size |  64 (128 w flip) |  32
training epochs |  128 |  64
warmup iterations | 6e4
|  |
TABLE V: Settings for EP Variants


# Separating Words from Every Start State
with Horner Automata

Nicholas Tran Santa Clara UniversitySanta Clara, CA 95053<EMAIL_ADDRESS>
###### Abstract

We show that a well-known family of deterministic finite automata $H_{b,m}$
can be used to distinguish distinct binary strings of the same length from
every start state. Further, we establish a lower bound of $\Omega(\sqrt{n/\log
n})$ and an upper bound of $O(\sqrt{n}\log n\log\log n)$ on the number of
states of $H_{b,m}$ necessary to achieve this type of separation. Our latter
result improves the currently best known $O(n)$ upper bound for arbitrary DFA.

##  1 Introduction

Given two distinct strings (or words) over some alphabet, we are interested in
the minimum size of deterministic finite automata that end in different states
after reading the strings for every (common) start state. We call this the
$\forall$-separation distance between strings, and when the alphabet is
nonunary, we use $D_{\forall}(n)$ to denote the largest $\forall$-separation
distance between two distinct strings of length $n$. This variant of the
separating words problem was recently introduced and studied in [10], where a
lower bound of $\Omega(\log n)$ and an upper bound of $n+1$ on
$D_{\forall}(n)$ were established. The main result of this paper is an
improved $O(\sqrt{n}\log n\log\log n)$ upper bound on $D_{\forall}(n)$.

The original separating words problem was studied in [5, 7, 4, 11, 3]. The
standard notion of separation words by deterministic finite automata requires
one string to be accepted and the other rejected. It is clearly equivalent to
the definition of separation stated initially in [5] that does not involve
accepting states: a deterministic finite automaton separates two strings if it
ends in different states after reading the strings for some (common) start
state. We use $D_{\exists}(n)$ to denote the largest separation distance of
this type between two distinct strings of length $n$ for nonunary alphabets.
The best known upper bound on $D_{\exists}(n)$ is $O(n^{1/3}\log^{7}n)$ [3],
and the best known lower bound on $D_{\exists}(n)$ is $\Omega(\log n)$ [4]. It
is known that the separation distances are tightly bound by $\log n$ for
strings of different lengths $m<n$ (in particular, for distinct strings over
unary alphabets), and that $D_{\exists}(n)$ and $D_{\forall}(n)$ do not depend
on the (nonunary) alphabet size. Table 1 lists values of $D_{\exists}(n)$ and
$D_{\forall}(n)$ for small values of $n$, obtained via exhaustive
search111These results were computed using a C++ program running on a Linux
workstation with Intel® Core™ i7-4790S CPU @ 3.20GHz and 16 GB RAM. .

$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$D_{\exists}(n)$ | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 5
$D_{\forall}(n)$ | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 5 | 5 | 5 | 5
Table 1: Values of $D_{\exists}(n)$ and $D_{\forall}(n)$ for $1\leq n\leq 18$.

If the separating automaton is required to end in different states for every
pair of start states, then the largest so-called $\forall^{2}$-separation
distance between two distinct strings of length $n$ is exactly $n+1$ and
unbounded between strings of different lengths (i.e., they may not be
separable). At the other extreme, if the separating automaton is required to
end in different states for some pair of start states, then the largest so-
called $\exists^{2}$-separation distance between two distinct strings
(regardless of lengths) is 2. These and other results can be found in [10].

The best lower bound of $\Omega(\log n)$ on $D_{\exists}(n)$ applies trivially
to $D_{\forall}(n)$; it is not known if a stronger lower bound holds for the
latter. On the other hand, the best upper bound of $O(n^{1/3}\log^{7}n)$ on
$D_{\exists}(n)$ does not readily apply to $D_{\forall}(n)$. In fact, it is
not immediately clear how to establish even a looser upper bound such as
$n+1$. In this paper we show how to adapt the technique of counting the number
of cyclotomic factors of certain polynomials [11, 3] to obtain an
$O(\sqrt{n}\log n\log\log n)$ upper bound on $D_{\forall}(n)$. Our result
improves the currently best known $O(n)$ upper bound obtained in [10].

Specifically, we interpret each nonempty binary string $s$ as the
representation of an integer $N_{s,b}$ in some base $b$ and show how to
compute $N_{s,b}\bmod{m}$ for some modulus $m$ using a familiar deterministic
finite automaton $H_{b,m}$ with $m$ states and dependent only on $b$ and $m$.
We then show that if $s$ and $t$ are distinct binary strings of length $n\geq
1$, then $N_{b,s}\not\equiv N_{b,t}\pmod{m}$ for some $0\leq b<m\in
O(\sqrt{n}\log n\log\log n)$. Hence $H_{b,m}$ $\exists$-separates $s$ and $t$,
and in fact we show that $H_{b,m}$ $\forall$-separates $s$ and $t$. On the
other hand, we show that for every $n\geq 1$, there are distinct binary
strings $s$ and $t$ of length $n$ such that the smallest $H_{b,m}$ that
$\forall$-separates $s$ and $t$ have $\Omega(\sqrt{n/\log n})$ states.

The rest of this paper is organized as follows. Section 2 reviews basic
definitions about separating words with automata and states some useful
number-theoretic facts. The next section contains the main results: Subsection
3.1 presents so-called Horner automata $H_{b,m}$ and shows how to use them to
$\forall$-separate strings, Subsection 3.2 proves an $\Omega(\sqrt{n/\log n})$
lower bound on the size of $H_{b,m}$ required to $\forall$-separate two
distinct binary strings of length $n$, and Subsection 3.3 establishes an
$O(\sqrt{n}\log n\log\log n)$ corresponding upper bound. Section 4 discusses
ideas for future work.

##  2 Preliminaries

The symbols of a string $s$ of length $n\geq 1$ from left to right are denoted
by $s_{0},s_{1},\ldots,s_{n-1}$. The natural and binary logarithms are denoted
by $\ln$ and $\log$ respectively. We use the following simplified definition
of deterministic finite automata that does not specify an initial state or
accepting states:

######  Definition 1.

A deterministic finite automaton (DFA) is a triple

$M=(Q,\Sigma,\delta),$

where $Q$ is a finite set of states, $\Sigma$ is an alphabet, and
$\delta:Q\times\Sigma\rightarrow Q$ is a transition function. We use $|M|$ to
denote the number of states of $M$ and refer to it as the size of $M$.

The extended transition function $\delta^{\prime}:Q\times\Sigma^{*}\rightarrow
Q$ is defined recursively:

  1. 1.

$\delta^{\prime}(q,\epsilon)=q$, where $\epsilon$ is the empty string, for
$q\in Q$;

  2. 2.

$\delta^{\prime}(q,xa)=\delta(\delta^{\prime}(q,x),a)$ for $a\in\Sigma$,
$x\in\Sigma^{*}$ and $q\in Q$.

The first and last states in the sequence of states that $M$ enters when
reading a string from left to right are called the start and end state
respectively.

######  Definition 2.

Let $x$ and $y$ be strings over an alphabet $\Sigma$. We say a DFA $M$

  * •

$\exists$-separates $x$ and $y$ if
$\delta^{\prime}(s,x)\not=\delta^{\prime}(s,y)$ for some $s\in Q$;

  * •

$\forall$-separates $x$ and $y$ if
$\delta^{\prime}(s,x)\not=\delta^{\prime}(s,y)$ for every $s\in Q$.

######  Example 1.

Let $s=0000\ 0000$ and $t=1111\ 1100$.

The two-state DFA in Fig. 1 (left) $\exists$-separates $s$ and $t$ because
$a=\delta^{\prime}(a,s)\not=\delta^{\prime}(a,t)=b$, and it is clearly a
smallest such automaton. On the other hand, this DFA does not
$\forall$-separate $s$ and $t$ because
$\delta^{\prime}(b,s)=\delta^{\prime}(b,t)=b$.

The four-state DFA in Fig. 1 (right) $\forall$-separates $s$ and $t$ because

$\displaystyle a=\delta^{\prime}(a,s)$ $\displaystyle\not=$
$\displaystyle\delta^{\prime}(a,t)=b,$ $\displaystyle b=\delta^{\prime}(b,s)$
$\displaystyle\not=$ $\displaystyle\delta^{\prime}(b,t)=a,$ $\displaystyle
c=\delta^{\prime}(c,s)$ $\displaystyle\not=$
$\displaystyle\delta^{\prime}(c,t)=a,$ $\displaystyle d=\delta^{\prime}(d,s)$
$\displaystyle\not=$ $\displaystyle\delta^{\prime}(d,t)=a.$

It is shown to be a smallest such automaton in [10].

Figure 1: The DFA on the left $\exists$-separates $0000\ 0000$ and $1111\
1100$ but does not $\forall$-separate them. The DFA on the right
$\forall$-separates the strings.

The following facts can be found in standard texts on number theory, e.g.,
[6]. The Prime Number Theorem states that $\pi(x)$, the number of primes less
than or equal to $x$, is approximately $x/\ln x$, i.e.,

$\lim_{x\to\infty}\frac{\pi(x)}{\frac{x}{\ln x}}=1.$

Bertrand’s postulate states that for every $n>1$, there is a prime $p$ such
that $n<p<2n$. For every integer $n\geq 1$, the $n^{\rm th}$ cyclotomic
polynomial $\Phi_{n}(x)$ is defined as the polynomial whose zeros are the
primitive $n^{\rm th}$ roots of unity:

$\Phi_{n}(x)=\prod_{\begin{subarray}{c}1\leq k\leq n\\\
\gcd(k,n)=1\end{subarray}}(x-e^{2\pi ik/n}).$

We list relevant properties of cyclotomic polynomials here. The coefficients
of $\Phi_{n}(x)$ are integers, and its degree is $\phi(n)$, the Euler’s
totient function; it is known that $\phi(n)\in\Omega(n/\log\log n)$ [8] and
that the function $x/\log\log x$ is increasing when $x\geq 6$ (e.g.,
Wolfram—Alpha). The cyclotomic polynomials are irreducible and co-prime over
$\mathbb{Q}$, i.e., $\gcd(\Phi_{n}(x),\Phi_{m}(x))=1$ for $n\not=m$. Finally,
$\Phi_{n}(x)$ divides $x^{n}-1$ for all $n\geq 1$.

######  Example 2.

The properties listed above can be seen to hold for the first few cyclotomic
polynomials:

$\displaystyle\Phi_{1}(x)$ $\displaystyle=$ $\displaystyle x-1,$
$\displaystyle\Phi_{2}(x)$ $\displaystyle=$ $\displaystyle x+1,$
$\displaystyle\Phi_{3}(x)$ $\displaystyle=$ $\displaystyle x^{2}+x+1,$
$\displaystyle\Phi_{4}(x)$ $\displaystyle=$ $\displaystyle x^{2}+1,$
$\displaystyle\Phi_{5}(x)$ $\displaystyle=$ $\displaystyle
x^{4}+x^{3}+x^{2}+x+1,$ $\displaystyle\Phi_{6}(x)$ $\displaystyle=$
$\displaystyle x^{2}-x+1.$

The set of integers modulo $m$ is denoted $\mathbb{Z}_{m}$, and the set of
polynomials in $x$ with integer coefficients is denoted $\mathbb{Z}[X]$. A
polynomial $P(x)\in\mathbb{Z}[X]$ is said to vanish modulo $m$ if $P(x)\equiv
0\pmod{m}$ for all $x\in\mathbb{Z}$. Lagrange’s theorem states that if
$P(x)\in\mathbb{Z}[X]$ has degree $n\geq 1$ and $p$ is a prime, then either
$P(x)$ has at most $n$ zeros modulo $p$, or all coefficients of $P(x)$ are
divisible by $p$. By Fermat’s little theorem, $x^{p}-x$ vanishes modulo $p$
when $p$ is prime.

We associate with each binary string $s$ of length $n\geq 1$ the polynomial

$s(x)=\sum_{j=0}^{n-1}s_{j}x^{n-1-j}$

with coefficients in $\mathbb{Z}_{2}$. If $s$ and $t$ are distinct binary
strings of length $n\geq 1$, $s(x)-t(x)$ is a nonzero polynomial of degree at
most $n-1$ with coefficients in $\\{-1,0,1\\}$.

######  Example 3.

Again, let $s=0000\ 0000$ and $t=1111\ 1100$. The associated polynomials are
$s(x)=0$ and $t(x)=x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}$. Their difference
$s(x)-t(x)$ is $-(x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2})$.

This difference polynomial vanishes modulo $2$ because

$\displaystyle-(0^{7}+0^{6}+0^{5}+0^{4}+0^{3}+0^{2})=0$ $\displaystyle\equiv$
$\displaystyle 0\pmod{2},$
$\displaystyle-(1^{7}+1^{6}+1^{5}+1^{4}+1^{3}+1^{2})=-6$ $\displaystyle\equiv$
$\displaystyle 0\pmod{2}.$

Similarly, it also vanishes modulo $3$ because

$\displaystyle-(0^{7}+0^{6}+0^{5}+0^{4}+0^{3}+0^{2})=0$ $\displaystyle\equiv$
$\displaystyle 0\pmod{3},$
$\displaystyle-(1^{7}+1^{6}+1^{5}+1^{4}+1^{3}+1^{2})=-6$ $\displaystyle\equiv$
$\displaystyle 0\pmod{3},$
$\displaystyle-(2^{7}+2^{6}+2^{5}+2^{4}+2^{3}+2^{2})=-252$
$\displaystyle\equiv$ $\displaystyle 0\pmod{3}.$

However, $s(x)-t(x)$ does not vanish modulo $5$ because

$-(1^{7}+1^{6}+1^{5}+1^{4}+1^{3}+1^{2})=-6\not\equiv 0\pmod{5}.$

We will see in the next section that the above observation can be deduced by
noting that

$x^{5}-x=x(x-1)(x+1)(x^{2}+1)$

does not divide $s(x)-t(x)$ over the rationals:

$\displaystyle-(x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2})$ $\displaystyle=$
$\displaystyle-x^{2}(x+1)(x^{2}-x-1)(x^{2}+x+1).$

##  3 Main Results

In this section we introduce Horner automata and show how to use them to
$\forall$-separate strings. We then establish almost matching lower bound and
upper bound on the size of the smallest Horner automata that
$\forall$-separate two distinct binary strings of length $n$.

###  3.1 Horner automata and $\forall$-separation

For $0\leq b<m$, let $H_{b,m}$ be the deterministic finite automaton with $m$
states $0$, $1$, $\ldots$, $m-1$ and transition function
$\delta(i,a)=(ib+a)\bmod{m}$ for $a\in\\{0,1\\}$; note that the input alphabet
is binary. The special cases $H_{2,m}$ are usually introduced in an
introductory course on automata theory to recognize binary strings
representing integers divisible by $m$. They are named Horner automata in [9],
because on binary input $s$ and start state $0$, they compute the value of the
associated polynomial $s(b)$ using Horner’s rule and end in state
$s(b)\bmod{m}$:

$\delta^{\prime}(0,s)=((\cdots((0b+s_{0})b+s_{1})b+\cdots+s_{n-2})b+s_{n-1})\bmod{m}=s(b)\bmod{m}.$

In other words, these automata “compute” $N_{s,b}\bmod m$, where $N_{s,b}$ is
the integer represented by binary string $s$ in base $b$ (but they are not the
smallest ones to do so [2]). We prove a slightly stronger statement of this
fact in the following lemma.

######  Lemma 1.

Let $0\leq b,i<m$ be integers and $s$ be a binary string of length $n\geq 1$.
Starting in state $i$, the Horner automaton $H_{b,m}$ ends in state
$(ib^{n}+s(b))\bmod{m}$ after reading $s$.

###### Proof.

By induction on $n$. When $n=1$, the string $s$ is just symbol $s_{0}$, and
the associated polynomial $s(x)$ is the constant polynomial $s_{0}$. Starting
in state $i$, $M_{b,m}$ ends in state

$\delta^{\prime}(i,s_{0})=(ib+s_{0})\bmod{m}=(ib^{1}+s(b))\bmod{m},$

after reading $s$, so the lemma holds.

Assume that the lemma holds for $n$ and let $s=s_{0}s_{1}\ldots s_{n}$ be a
binary string of length $n+1$. Starting in state $i$ on input $s$, the
automaton $H_{b,m}$ ends in state

$\displaystyle\delta^{\prime}(i,s)$ $\displaystyle=$
$\displaystyle\delta^{\prime}(i,s_{0}\ldots s_{n-1}s_{n})$ $\displaystyle=$
$\displaystyle\delta(\delta^{\prime}(i,s_{0}\ldots s_{n-1}),s_{n})$
$\displaystyle=$
$\displaystyle\delta((ib^{n}+\sum_{j=0}^{n-1}s_{j}b^{n-1-j})\bmod{m},s_{n})$
$\displaystyle=$
$\displaystyle(ib^{n+1}+\sum_{j=0}^{n-1}(s_{j}b^{n-j})+s_{n})\bmod{m}$
$\displaystyle=$ $\displaystyle(ib^{n+1}+\sum_{j=0}^{n}s_{j}b^{n-j})\bmod{m}$
$\displaystyle=$ $\displaystyle(ib^{n+1}+s(b))\bmod{m}.$

∎

######  Example 4.

Fig. 2 shows the automaton $H_{2,5}$ on the left. On input $s=10\ 1111$ and
start state $0$, it ends in state
$s(2)\bmod{5}=2^{5}+2^{3}+2^{2}+2^{1}+2^{0}=47\bmod{5}=2$. In contrast, on
input $t=11\ 1011$ and start state $0$, it ends in state
$t(2)\bmod{5}=2^{5}+2^{4}+2^{3}+2^{1}+2^{0}=59\bmod{5}=4$. Thus, $H_{2,5}$
$\exists$-separates $s$ and $t$, and in fact, it $\forall$-separates $s$ and
$t$ due to Lemma 1. We demonstrate in general this important property of
Horner automata below.

Figure 2: Horner automata $H_{2,5}$ (left) and $H_{1,2}$ (right)

It is natural to study the separation distance between two binary strings of
the same length by Horner automata. We define this notion formally and study
its properties here.

######  Definition 3.

  1. 1.

The Horner distance between two distinct binary strings $s$ and $t$, denoted
by $d_{H}(s,t)$, is the smallest $m$ such that $H_{b,m}$ $\exists$-separates
$s$ and $t$ for some $0\leq b<m$.

  2. 2.

The Horner separation distance, denoted by $D_{H}(n)$, is the maximum Horner
distance over all pairs of distinct binary strings $s$ and $t$ of length $n$,
for $n\geq 1$.

We now show that the Horner distance between two distinct binary strings $s$
and $t$ of the same length is always defined, and furthermore, it is an upper
bound of the $\forall$-distance between $s$ and $t$.

######  Lemma 2.

Let $s$ and $t$ be binary strings of length $n$. The following are equivalent:

  1. 1.

$s$ and $t$ are distinct;

  2. 2.

$s$ and $t$ are $\exists$-separated by $H_{b,m}$ for some $0\leq b<m\leq 2n$;

  3. 3.

$s$ and $t$ are $\forall$-separated by $H_{b,m}$ for some $0\leq b<m\leq 2n$.

###### Proof.

(1) $\Rightarrow$ (2): Let $s$ and $t$ be two distinct binary strings of
length $n$. When $n=1$, there is only one pair of distinct strings $0$ and
$1$, and they are $\exists$-separated by $H_{1,2}$ (shown in Fig. 2 on the
right) when started in state 0. For $n>1$, by Bertrand’s postulate, there is a
prime $p$ such that $n<p<2n$. The polynomial $d(x)=s(x)-t(x)$ has degree at
most $n-1$, coefficients in $\\{-1,0,1\\}$, and not all coefficients are zero,
because $s$ and $t$ are distinct. Thus, by Lagrange’s theorem $d(x)$ has at
most $n-1$ zeros in $\mathbb{Z}_{p}$, so there exists $0\leq b<p$ such that
$d(b)\not\equiv 0\pmod{p}$. Since $d(b)=s(b)-t(b)$, we have
$s(b)-t(b)\not\equiv 0\pmod{p}$, or $s(b)\not\equiv t(b)\pmod{p}$. Thus,
$H_{b,p}$ $\exists$-separates $s$ and $t$ on start state $0$.

(2) $\Rightarrow$ (3): Suppose $H_{b,m}$ separates binary strings $s$ and $t$
of length $n$ on start state $i_{0}$ for some $0\leq b,i_{0}<m\leq 2n$. By
Lemma 1, $i_{0}b^{n}+s(b)\not\equiv i_{0}b^{n}+t(b)\pmod{m}$, so
$ib^{n}+s(b)\not\equiv ib^{n}+t(b)\pmod{m}$ for all $0\leq i<m$. Thus, $s$ and
$t$ are $\forall$-separated by $H_{b,m}$.

(3) $\Rightarrow$ (1): Suppose $s$ and $t$ are binary strings of length $n$
that are $\forall$-separated by $H_{b,m}$ for some $0\leq b<m\leq 2n$. Then
$s(b)\not\equiv t(b)\pmod{m}$, so $s(x)\not=t(x)$, and hence $s\not=t$. ∎

###  3.2 Lower bound on the Horner separation distance $D_{H}(n)$

We use a simple information-theoretic argument to show that the Horner
separation distance $D_{H}(n)$ is at least $\Omega(\sqrt{n/\log n})$.

######  Theorem 1.

$D_{H}(n)\in\Omega(\sqrt{n/\log n})$ for $n\geq 1$.

###### Proof.

Let $s$ and $t$ be distinct binary strings of length $n$. If they cannot be
$\exists$-separated by a Horner automaton of size $M$ or less, the values of
their polynomials $s(x)$ and $t(x)$ must be congruent modulo $m$ for all
$0\leq b<m$ and $2\leq m\leq M$. The congruence classes of these values can be
encoded in a binary string (called a signature) of length at most

$\sum_{m=2}^{M}\sum_{b=0}^{m-1}(\log m)\leq\sum_{m=2}^{M}\sum_{b=0}^{m-1}(\log
M)\in O(M^{2}\log M)\in O(M^{2}\log n)$

due to the upper bound on $M$ in terms of $n$ given by Lemma 2. There are
$2^{O(M^{2}\log n)}$ such signatures and $2^{n}$ binary strings of length $n$,
so to ensure that different $s$ and $t$ have different signatures and
$\exists$-separable by a Horner automaton of size $D_{H}(n)$, we must have
$2^{n}\leq 2^{O(D_{H}^{2}(n)\log n)}$, or $n\in O(D_{H}^{2}(n)\log n)$, and
hence $D_{H}(n)\in\Omega(\sqrt{n/\log n})$. ∎

###  3.3 Upper bound on the Horner separation distance $D_{H}(n)$

We begin with an observation that for large enough prime $p$, a polynomial
$P(x)$ whose coefficients are in $\\{-1,0,1\\}$ vanishes modulo $p$ if and
only it is divisible by $x^{p}-x$.

######  Lemma 3.

Let $P(x)=\sum_{j=0}^{n}p_{j}x^{j}$ be a polynomial of degree $n\geq 0$ with
coefficients $p_{j}\in\\{-1,0,1\\}$, and let $p\geq 1+\sqrt{n}$ be a prime.
The polynomial $P(x)$ vanishes modulo $p$ if and only if $P(x)=(x^{p}-x)Q(x)$
for some $Q(x)\in\mathbb{Z}[x]$.

###### Proof.

Suppose $P(x)=(x^{p}-x)Q(x)$ for some polynomial $Q(x)\in\mathbb{Z}[x]$. By
Fermat’s little theorem, $x^{p}-x$ vanishes modulo $p$, so $P(x)$ also
vanishes modulo $p$.

Conversely, suppose $P(x)$ vanishes modulo $p$. Since $P(0)=p_{0}\equiv
0\pmod{p}$, and $p_{0}\in\\{-1,0,-1\\}$, we have $p_{0}=0$. The division
algorithm for integral polynomials says that

$P(x)=(x^{p}-x)Q(x)+R(x)$

for some $Q(x)=\sum_{j=0}^{n-p}q_{j}x^{j}$,
$R(x)=\sum_{j=0}^{p-1}r_{j}x^{j}\in\mathbb{Z}[x]$, where the degree of $R(x)$
is less than $p$. Since both $P(x)$ and $x^{p}-x$ vanish modulo $p$, so does
$R(x)$. Because $R(x)$ has $p$ zeros modulo $p$ but its degree is less than
$p$, by Lagrange’s theorem, all coefficients of $R(x)$ must be divisible by
$p$. We now show that the coefficients of $R(x)$ have absolute values at most
$p-1$, and hence must all be zeros, i.e., $R(x)=0$.

Expanding term by term both sides of $P(x)=(x^{p}-x)Q(x)+R(x)$, we have

$\displaystyle\sum_{j=0}^{n}p_{j}x^{j}$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{n-p}q_{j}x^{j+p}-\sum_{j=0}^{n-p}q_{j}x^{j+1}+\sum_{j=0}^{p-1}r_{j}x^{j}$
$\displaystyle=$
$\displaystyle\sum_{j=n-p+2}^{n}q_{j-p}x^{j}+\sum_{j=p}^{n-p+1}(q_{j-p}-q_{j-1})x^{j}+\sum_{j=1}^{p-1}(r_{j}-q_{j-1})x^{j}+r_{0}.$

Comparing coefficients on the left and right sides, we see that the constant
coefficient of $R(x)$ is 0, and the absolute values of the leftmost $p-1$
coefficients of $Q(x)$ are bounded by 1, because

$\displaystyle r_{0}$ $\displaystyle=$ $\displaystyle p_{0}=0$
$\displaystyle|q_{j-p}|$ $\displaystyle=$ $\displaystyle|p_{j}|\leq 1,\text{\
\ \ \ }\ \ n-p+2\leq j\leq n$

Similarly, we see that the next leftmost $p-1$ coefficients of $Q(x)$ have
absolute values bounded by 2, because their differences with the first
leftmost $p-1$ coefficients are bounded in absolute value by 1, as can be seen
below after changing the range of $j$:

$\displaystyle|q_{j-p}-q_{j-1}|$ $\displaystyle\leq$ $\displaystyle 1,\text{\
\ \ \ }\ \ n-2p+3\leq j\leq n-p+1$ $\displaystyle|q_{j-2p+1}-q_{j-p}|$
$\displaystyle\leq$ $\displaystyle 1,\text{\ \ \ \ }\ \ n-p+2\leq j\leq n$

Repeating this argument, we conclude that the next leftmost $p-1$ coefficients
of $Q(x)$ have absolute values bounded by 3, and so on. Since there are
$\lceil\frac{n}{p-1}\rceil$ such groups (the constant coefficient is zero), we
conclude that the absolute values of coefficients of $R(x)$ are bounded by
$\lceil\frac{n}{p-1}\rceil$ and hence by $p-1$ because

$\displaystyle\left\lceil\frac{n}{p-1}\right\rceil$ $\displaystyle\leq$
$\displaystyle\left\lceil\frac{n}{1+\sqrt{n}-1}\right\rceil$ $\displaystyle=$
$\displaystyle\left\lceil\sqrt{n}\right\rceil$ $\displaystyle<$ $\displaystyle
1+\sqrt{n}$ $\displaystyle\leq$ $\displaystyle p.$

∎

######  Example 5.

Let $s=0000\ 1010\ 0000\ 0000$ and $t=0000\ 0000\ 0010\ 1000$. The associated
polynomials are $s(x)=x^{11}+x^{9}$ and $t(x)=x^{5}+x^{3}$. The polynomial
$P(x)=s(x)-t(x)=x^{11}+x^{9}-x^{5}-x^{3}$ has the following irreducible
factors over the rationals:

$\displaystyle P(x)=x^{11}+x^{9}-x^{5}-x^{3}$ $\displaystyle=$ $\displaystyle
x^{3}(x-1)(x+1)(x^{2}+1)(x^{2}-x+1)(x^{2}+x+1).$

Primes 5, 7, 11 are all greater than $1+\sqrt{11}$. Since

$\displaystyle x^{5}-x=x(x-1)(x+1)(x^{2}+1)$ $\displaystyle|$ $\displaystyle
P(x),$ $\displaystyle x^{7}-x=x(x-1)(x+1)(x^{2}-x+1)(x^{2}+x+1)$
$\displaystyle|$ $\displaystyle P(x),$ $\displaystyle
x^{11}-x=x(x-1)(x+1)(x^{4}-x^{3}+x^{2}-x+1)(x^{4}+x^{3}+x^{2}+x+1)$
$\displaystyle\not|$ $\displaystyle P(x),$

it follows from Lemma 3 that $P(x)$ vanishes modulo 5 and 7, but not modulo
11. Exhaustive search shows that $d_{H}(s,t)=9$ while $d_{\forall}(s,t)=4$.

We are now ready to prove an $O(\sqrt{n}\log n\log\log n)$ upper bound on
$D_{H}(n)$ using Lemma 3. Let $s$ and $t$ be distinct binary strings of length
$n$, and let $P(x)=s(x)-t(x)$, whose degree is at most $n-1$. If $P(x)$
vanishes modulo $p$ for some $p\geq 1+\sqrt{n-1}$, then $P(x)$ is divisible by
$x^{p}-x$, which is in turn divisible by $\Phi_{p-1}(x)$. Since these
cyclotomic polynomials are co-prime, the sum $\delta$ of their degrees is
bounded above by $n-1$, which implies the stated upper bound on $d_{H}(s,t)$.

######  Theorem 2.

$D_{H}(n)\in O(\sqrt{n}\log n\log\log n)$.

###### Proof.

Let $s$ and $t$ be distinct binary strings of length $n$, and suppose the
Horner distance $d_{H}(s,t)$ is $M\sqrt{n}$, so that $P(x)=s(x)-t(x)$, whose
degree is at most $n-1$, is congruent to the zero polynomial mod $p$ for all
primes $p<M\sqrt{n}$.

By Lemma 2, $M\sqrt{n}\leq 2n$, so $M\leq 2\sqrt{n}$. By Lemma 3, for each
such prime $p>\sqrt{n}$, $P(x)$ is divisible by $x^{p}-x=x(x^{p-1}-1)$ and
hence divisible by the cyclotomic polynomial $\Phi_{p-1}(x)$, whose degree is
$\phi(p-1)\in\Omega((p-1)/\log\log(p-1))$. Since these cyclotomic polynomials
are co-prime, the sum $\delta$ of their degrees is at most $n-1$. There are
approximately

$\frac{M\sqrt{n}}{\ln(M\sqrt{n})}-\frac{\sqrt{n}}{\ln\sqrt{n}}>\frac{M\sqrt{n}}{\ln(2\sqrt{n}\sqrt{n})}-\frac{\sqrt{n}}{\ln\sqrt{n}}\geq\alpha\frac{M\sqrt{n}}{\log
n}$

primes $p$ in the range $[\sqrt{n},M\sqrt{n}]$ by the Prime Number Theorem,
for some constant $\alpha$. Because the function $x/\log\log x$ is eventually
increasing, each $\Phi_{p-1}(x)$ contributes at least
$\beta\sqrt{n}/\log\log(\sqrt{n})$, for some constant $\beta$, to the degree
sum $\delta$, which is at most $n-1$, so

$\left(\frac{\alpha
M\sqrt{n}}{\log{n}}\right)\left(\frac{\beta\sqrt{n}}{\log\log
n}\right)=\left(\frac{\alpha\beta Mn}{\log n\log\log n}\right)\leq\delta<n.$

It follows that $M\in O(\log n\log\log n)$, and hence $d_{H}(s,t)\in
O(\sqrt{n}\log n\log\log n)$. Since this holds for arbitrary pairs of distinct
binary strings of length $n$, we conclude that $D_{H}(n)\in O(\sqrt{n}\log
n\log\log n)$. ∎

Because the more restrictive separation distance $D_{H}(n)$ is an upper bound
on $D_{\forall}(n)$, we obtain our main result.

######  Theorem 3.

$D_{\forall}(n)\in O(\sqrt{n}\log n\log\log n)$.

##  4 Conclusion

We show how to use Horner automata $H_{b,m}$ to $\forall$-separate two
distinct binary strings of length $n$ and establish almost matching lower and
upper bounds on the minimum value of such $m$. Closing the gap between these
two bounds is an interesting open problem, as is the question of whether other
families of automata can be designed to achieve better lower and upper bounds
on the $\forall$-separation distance.

## Acknowledgments

Detailed comments and suggestions by the anonymous referees help improve the
presentation of this paper.

## References

  * [1]
  * [2] B. Alexeev (2004): _Minimal DFA for Testing Divisibility_.  Journal of Computer and System Sciences 69(2), p. 235–243, 10.1016/j.jcss.2004.02.001.
  * [3] Z. Chase (2021): _Separating Words and Trace Reconstruction_.  In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 21–31, 10.1145/3406325.3451118.
  * [4] E. D. Demaine, S. Eisenstat, J. Shallit & D. A. Wilson (2011): _Remarks on Separating Words_.  In M. Holzer, M. Kutrib & G. Pighizzini, editors: Proceedings of the 13th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Lecture Notes in Computer Science 6808, Springer, Berlin, Heidelberg, pp. 147–157, 10.1007/978-3-642-22600-7.
  * [5] P. Goralčík & V. Koubek (1986): _On Discerning Words by Automata_.  In L. Kott, editor: Proceedings of the 13th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science 226, Springer, Berlin, Heidelberg, pp. 116–122, 10.1007/3-540-16761-7_61.
  * [6] I. Niven, H. S. Zuckerman & H. L. Montgomery (1991): _An Introduction to the Theory of Numbers_.  Wiley.
  * [7] J. M. Robson (1989): _Separating strings with small automata_.  Information Processing Letters 30(4), pp. 209–214, 10.1016/0020-0190(89)90215-9.
  * [8] J. B. Rosser & L. Schoenfeld (1962): _Approximate formulas for some functions of prime numbers_.  Illinois Journal of Mathematics 6(1), pp. 64–94, 10.1215/ijm/1255631807.
  * [9] K. Sutner (2009): _Divisibility and State Complexity_.  The Mathematica Journal 11(3), pp. 430–445, 10.3888/tmj.11.3-8.
  * [10] N. Tran (2022): _Variations of the Separating Words Problem_.  In P. Caron & L. Mignot, editors: Proceedings of the 26th International Conference on Implementation and Application of Automata (CIAA), Lecture Notes in Computer Science 13266, Springer, Berlin, Heidelberg, pp. 165–176, 10.1007/978-3-031-07469-1_13.
  * [11] M. N. Vyalyi & R. A. Gimadeev (2014): _Separating words by occurrences of subwords_.  Journal of Applied and Industrial Mathematics 8(2), pp. 293–299, 10.1134/S1990478914020161.