# TLEX: An Efficient Method for Extracting Exact Timelines from TimeML
Temporal Graphs

Mustafa Ocal
Knight Foundation School of Computing and Information Sciences
Florida International University
<EMAIL_ADDRESS>
&Ning Xie
Knight Foundation School of Computing and Information Sciences
Florida International University
<EMAIL_ADDRESS>
&Mark Finlayson
Knight Foundation School of Computing and Information Sciences
Florida International University
<EMAIL_ADDRESS>

###### Abstract

A timeline provides a total ordering of events and times, and is useful for a
number of natural language understanding tasks. However, qualitative temporal
graphs that can be derived directly from text—such as TimeML
annotations—usually explicitly reveal only partial orderings of events and
times. In this work, we apply prior work on solving point algebra problems to
the task of extracting timelines from TimeML annotated texts, and develop an
exact, end-to-end solution which we call tlex (TimeLine EXtraction). tlex
transforms TimeML annotations into a collection of timelines arranged in a
trunk-and-branch structure. Like what has been done in prior work, tlex checks
the consistency of the temporal graph and solves it; however, it adds two
novel functionalities. First, it identifies specific relations involved in an
inconsistency (which could then be manually corrected) and, second, tlex
performs a novel identification of sections of the timelines that have
indeterminate order, information critical for downstream tasks such as
aligning events from different timelines. We provide detailed descriptions and
analysis of the algorithmic components in tlex, and conduct experimental
evaluations by applying tlex to 385 TimeML annotated texts from four corpora.
We show that 123 of the texts are inconsistent, 181 of them have more than one
“real world” or main timeline, and there are 2,541 indeterminate sections
across all four corpora. A sampling evaluation showed that tlex is 98–100%
accurate with 95% confidence along five dimensions: the ordering of time-
points, the number of main timelines, the placement of time-points on main
versus subordinate timelines, the connecting point of branch timelines, and
the location of the indeterminate sections. We provide a reference
implementation of tlex, the extracted timelines for all texts, and the manual
corrections to the temporal graphs of the inconsistent texts.

_Keywords_ Timeline, TimeML, Temporal Reasoning, Temporal Information
Extraction

##  1 Introduction

A timeline is a data structure that organizes events and times in a total
ordering. Timelines are useful for a number of natural language understanding
tasks, such as question answering, which may require understanding the overall
temporal order of events to produce the correct answer (Saquete et al., 2004);
cross-document event co-reference (CDEC) and cross-document alignment, whose
accuracy can be improved by access to a total ordering of events (Navarro-
Colorado and Saquete, 2016); and summarization and visualization (Liu et al.,
2012), where timelines can enhance human understanding of the events as well
as the temporal structure of the texts.

Unfortunately, timelines are rarely explicit in text, and usually cannot be
extracted directly. Instead, texts usually explicitly reveal only partial
orderings of events and times. Such partial information can be used—either
through automatic analyzers (Verhagen et al., 2005), or manual annotation
(Pustejovsky et al., 2003a), or some combination of both—to construct a
temporal graph labeled in some temporal representation language, such as a
temporal algebra (Allen, 1983) or TimeML (Sauri et al., 2006).

For temporal graphs labeled with a temporal algebra (Barták et al., 2014),
prior work in the field of Qualitative Spatial and Temporal Reasoning (QSTR)
has shown how to extract an exact timeline (Kreutzmann and Wolter, 2014; van
Beek, 1992; Gereveni and Schubert, 1995) that represents one possible solution
of total ordering. However, this approach does not work for natural language
involving temporal information that cannot be encoded in a strictly temporal
algebra (i.e., expressions of possible, counterfactual, or conditional
worlds—called subordinated events here), which is the reason why schemes such
as TimeML were developed. Also, natural language is often ambiguous, hence it
is useful to know which portions of a timeline are indeterminate—that is, have
multiple possible orderings all consistent with the temporal graph.

There has been some prior work in the field of Natural Language Processing
(NLP) on extracting timelines from TimeML graphs using machine learning, but
these solutions fall short in dealing with all possible relations and can
result in outputs that contain ordering errors (see §2.3). These errors are a
natural consequence of using statistical approaches to solve the problem.

In this work, we apply the theoretical formalism and techniques from QSTR to
TimeML annotated texts, formulate timeline extraction as a topological sort
problem, and show that one can achieve a theoretically exact solution, unlike
prior NLP approaches. Furthermore, our framework handles all possible temporal
relations (including aspectual and subordination relations) and detects
indeterminacy. Specifically, we present tlex (TimeLine EXtraction), a method
for extracting a set of timelines from a TimeML annotated text, which handles
all TimeML relations and achieves perfect accuracy modulo the correctness of
an underlying TimeML graph. tlex outputs multiple timelines, one for each
temporally connected subgraph, including subordinated timelines which
represent possible (modal), counterfactual, or conditional situations
(subordination is a representational feature of TimeML). These subordinated
timelines are connected to the main timeline in a trunk-and-branch timeline
structure.111It is worth mentioning that, although tlex is the first system
that converts a TimeML graph into trunk-and-branch timeline structure, the
idea of separating subordinated events in annotations was previously
introduced in the multi-axis annotation scheme model (Ning et al., 2018), in
which the authors defined different axis for different types of events in the
annotations such as intention/opinion events (on an orthogonal axis), generic
events (on a parallel axis), negations (not on an axis), and static events
(other axis). Like prior work, tlex checks the TimeML graph for consistency
and performs topological sorting to produce a timeline but goes further by
automatically identifying inconsistent subgraphs, which allows texts to be
manually corrected. It also identifies indeterminacy in ordering, a common
consequence of the ambiguity in natural languages.

We provide a formal proof of tlex’s correctness, as well as experimental
evaluations using 385 manually annotated texts comprising 129,860 words across
four corpora. This revealed 123 inconsistent temporal graphs, for which we
provide manual corrections. We also checked five different features of the
extracted timelines using a sampling evaluation. Our measurements show that
tlex achieves an accuracy of 98–100% with 95% confidence on all these
measurements. We release (a) a reference implementation of the tlex algorithm
in Java, (b) the timelines extracted from the corpora, (c) corrections to the
corpora, and (d) code to reproduce our
experiments222https://cognac.cs.fiu.edu/jtlex/.

There are four main contributions of this work. First, we describe the tlex
algorithm in detail, providing a clear explanation of how it works, a formal
proof of its correctness, and a reference implementation. Second, we introduce
a new indeterminacy marked trunk-and-branch timeline structure as tlex’s final
output. This structure separates main timelines (the “real world” or the
trunks) from subordinated timelines (the “possible worlds” or the branches).
This explicit recognition of the separation between “real world” and other
types of events is important in the semantics of natural language and has not
been dealt with in TimeML-to-timeline conversion work before. The
identification of indeterminacy in timelines is also novel. Third, we
demonstrate a new technique for identifying the specific temporal links that
contribute to temporal inconsistency, which allows targeted manual correction
of inconsistent TimeML annotations. Last, we experimentally evaluate tlex on
four TimeML corpora. Through a sampling evaluation, tlex’s performance is
found to be accurate within error bounds, confirming our theoretical results.

The rest of this paper is organized as follows. First, we discuss related
work, which we build upon and extend (§2). Second, we provide a detailed
description of tlex, breaking the procedure into five main steps, and present
proof of correctness and time complexity analysis for each step (§3). We then
describe our experimental evaluations and results (§4). We conclude with a
discussion of possible future work (§5) and a list of the contributions (§6).

##  2 Background and Related Work

###  2.1 Temporal Algebras & Reasoning

####  2.1.1 Interval Algebra

Allen’s interval algebra (Allen, 1983) is a calculus for temporal reasoning
that defines possible relations between a pair of time intervals and the
inference rules for relation compositions. Allen’s algebra was one of the
first attempts to computationally model temporal knowledge and temporal
reasoning. In this formalism, every event is abstracted as a time interval
$I$, which comprises a start point ($I^{-}$) and end time-point ($I^{+}$),
where the start point comes strictly before the end point ($I^{-}<I^{+}$). Two
intervals can be related by a set of $13$ mutually exclusive _basic_ temporal
relations: before, meets, overlaps, starts, during, and finishes, their
inverses, and equal. Allen’s interval algebra allows any subset of these $13$
basic relations to form a general relation (hence there are in total $2^{13}$
relations); two intervals $A$ and $B$ can be related by a basic relation as
$A$ before $B$, or by a more complex relation such as $A$ {before, during,
starts} $B$ when we are less certain about their temporal relation. Allen
presented a composition table for composing pairs of temporal relations, which
can be used to infer the temporal relation between intervals $A$ and $C$ given
the relation between $A$ and $B$ and the relation between $B$ and $C$. A
fundamental question in Allen’s algebra is the following _satisfiability_
problem: given $n$ interval $I_{1},\ldots,I_{n}$ and $m$ pairwise relations
among these intervals, does there exist a _configuration of intervals_ 333A
_configuration_ for a finite set of intervals
$\mathcal{I}=\\{I_{1},\ldots,I_{n}\\}$ is a set of $n$ bounded and closed
intervals (Ligozat, 2013, [pp. 9). More formally, a configuration is a
function $C:\mathcal{I}\to\mathbb{R}\times\mathbb{R}$ satisfying the property
that, for every $1\leq i\leq n$, if $C(I_{i})=\langle a_{i},b_{i}\rangle$
(i.e., if interval $I_{i}$ is mapped to the closed interval $[a_{i},b_{i}]$)
then $-\infty<a_{i}\leq b_{i}<\infty$. that satisfies all the relations?
Unfortunately, it was shown that the satisfiability problem is NP-complete
(Vilain and Kautz, 1986; Vilain et al., 1990).

Using Allen’s algebra, we can construct a _temporal graph_ from texts by
viewing events and times as intervals and representing them as the vertices of
the graph, and translating the relations between two events/times expressed in
natural language into Allen’s temporal relations and representing them as the
labels of the edges in the graph. Allen’s approach is referred to as a
qualitative temporal algebra because it does not represent exact times or
durations. A special type of temporal graph called an _atomic_ temporal graph,
in which all edge labels are basic relations, is of particular importance for
our purposes.

In a great deal of later work, Allen’s qualitative framework was generalized
and extended to the quantitative case, where time-points and durations are
given specific metric values. Researchers have proved quite a number of formal
results concerning both qualitative and quantitative formalisms (reviewed in
Barták et al. (2014)). Of particular importance are those results related to
checking the _consistency_ of temporal graphs, because a timeline can only be
constructed for consistent temporal graphs. To check the consistency of graphs
constructed using his algebra, Allen developed a polynomial time, constraint-
propagation type algorithm that repeatedly uses the composition table to
reconcile the relation between every pair of vertices, to ensure that their
relation is consistent with those relations imposed by all length-two paths
between them (so-called _path consistency_) (Allen, 1983). However, the
algorithm does not detect all inconsistencies, and it was later shown that
checking the consistency of general temporal graphs with all Allen relations
is NP-complete (Vilain and Kautz, 1986; Vilain et al., 1990), which makes the
task intractable under the commonly believed $\mathcal{P}\neq\mathcal{NP}$
assumption.

Because the full power of Allen’s interval algebra is likely to be
intractable, many researchers introduced tractable subclasses of Allen’s
algebra (Freksa, 1992; Nebel and Bürckert, 1995; Vilain et al., 1990). In a
celebrated paper (Nebel and Bürckert, 1995), a subclass called ORD-HORN is
shown to be the unique maximal tractable subclass of the full Allen algebra:
its consistency can be checked in polynomial time by the path-consistency
algorithm while checking any subclass that is greater than the ORD-HORN
subclass is NP-complete.

####  2.1.2 Point Algebra

Introduced by Vilain and Kautz (1986), the point algebra (PA) is a symbolic
calculus intended to work with qualitative ordering constraints between pairs
of time-points; for systematic treatments, see (Barták et al., 2014) and
references therein. PA defines three basic temporal constraints between two
time-points: $<$, $>$, and $=$. If there is no information between two time-
points $a$ and $b$, then we say $a$ {$<$, $>$, $=$} $b$. Temporal reasoning in
PA is much more efficient since it has only three basic relations. For
instance, the CSPAN algorithm checks the consistency of a PA temporal graph in
$O(n^{2})$ time, where $n$ is the number of time-points in the graph (van
Beek, 1992).

An interval sub-algebra of Allen’s algebra is called _pointisable_ if its
relations can be equivalently defined by a PA on the start and end points of
the intervals involved (Leeuwenberg and Moens, 2019). For example, it is easy
to check that $A$ before $B$ is equivalent to the constraints imposed by the
PA temporal graph in which $A^{-},A^{+},B^{-}$ and $B^{+}$ are the nodes and
each of the $12$ edges is labeled with an appropriate basic $<$ or $>$
relation (according to the ordering $A^{-}<A^{+}<B^{-}<B^{+}$). Moreover, it
can be easily verified that all basic relations are pointisable. However, one
can also show that $A$ {before, before_inverse} $B$ cannot be represented as
PA constraints on the same set of $4$ time-points. In fact, it is known that
there are only $167$ pointisable relations among all $2^{13}-1$ non-null
relations in Allen’s algebra. The translation of the basic Allen’s algebra
relations into PA relations is shown in Table 1.

Allen’s Algebra | TimeML | Point Algebra444Here we omit the trivial relations $I^{-}<I^{+}$ for all intervals $I$ involved to save space.
---|---|---
A Before B | A before B | $(A^{+}<B^{-})$
A After B | A after B | $(B^{+}<A^{-})$
A Meets B | A ibefore B | $(A^{+}=B^{-})$
A MetBy B | A iafter B | $(B^{+}=A^{-})$
A Starts B | A begins B | $(A^{-}=B^{-})\land(A^{+}<B^{+})$
A StartedBy B | A begun_by B | $(A^{-}=B^{-})\land(B^{+}<A^{+})$
A Finishes B | A ends B | $(B^{-}<A^{-})\land(A^{+}=B^{+})$
A FinishedBy B | A ended_by B | $(A^{-}<B^{-})\land(A^{+}=B^{+})$
A During B | A includes B | $(A^{-}<B^{-})\land(B^{+}<A^{+})$
A DuringInverse B | A is_included B | $(B^{-}<A^{-})\land(A^{+}<B^{+})$
A Equals B | A simultaneous B |  $(A^{-}$ = $B^{-})\land(A^{+}$ = $B^{+})$
| A identity B | $(A^{-}=B^{-})\land(A^{+}=B^{+})$
| A during B | $(B^{-}=A^{-})\land(A^{+}=B^{+})$
| A during_inv B | $(A^{-}=B^{-})\land(B^{+}=A^{+})$
| A initiates B | same as A begins B
| A culminates B | same as A ends B
| A terminates B | same as A ends B
| A continues B | same as A is_included B
| A reinitiates B | same as A is_included B
Table 1: Translation of the Allen’s Algebra relation and TimeML temporal &
aspectual relations into basic temporal relations between interval start and
end points. For an interval $I$ (an event or a time), the start point of the
interval is denoted by $I^{-}$ and the end point is denoted by $I^{+}$.

Allen’s interval algebra and point algebra (PA) are actually subclasses of a
more general problem called _Temporal Constraint Satisfaction Problems_
(TCSPs) (Dechter et al., 1991). In a TCSP, time-points are represented as a
set of variables, and temporal information is represented by a set of unary or
binary constraints over these variables, each specifying a set of permitted
intervals. A special case of TCSP, _Simple Temporal Problem_ (STP), was also
proposed and studied in (Dechter et al., 1991). The input to an STP is a set
of time-point variables together with constraints that bound the difference
between pairs of these variables, and the output is required to be a succinct
representation of the set of all possible assignments to time-point variables
that meet those constraints. Because STP is solvable in polynomial time and at
the same time captures much of the characteristics of temporal constraint
problems in real life, it has been extensively studied and applied in a wide
range of fields, such as planning, scheduling, robotics, and control theory.
For more background on STP and recent extensions, interested readers are
referred to (Ostuni et al., 2021).

###  2.2 Temporal Information Extraction and Annotation in Text

####  2.2.1 TIDES

Because of the utility of temporal frameworks for reasoning about time, and
also the relevance of time to understanding natural language, researchers in
Natural Language Processing (NLP) have sought to apply temporal algebras to
text understanding. This requires annotation schemes that would allow a person
or a machine to annotate a text for the time-points, events, and temporal
relations expressed.

Time expressions (TIMEXes) are sequences of tokens (words, numbers, or
characters) in text that denote time, including expressions of when something
happens, how often something occurs, or how long something takes. Starting
from the early 2000s, researchers developed a sequence of TIMEX annotation
schemes (Setzer, 2001; Ferro et al., 2001; Pustejovsky et al., 2003b). This
allows the annotation of expressions such as at 3 p.m. (when), or for 1 hour
(how long). Because events are also involved in temporal relations, these
approaches were extended into schemes for capturing both times and events. For
example, the Translingual Information Detection, Extraction, and Summarization
scheme (TIDES) (Ferro et al., 2001) integrates TIMEX2 expressions as well as a
scheme for annotating events. TIDES includes annotations for temporal
expressions, events, and temporal relations. TIDES uses only six temporal
relation types to represent the relations between events, therefore it
provides only limited temporal information from texts.

Figure 1: The 14 temporal and 5 aspectual TimeML link types. Temporal links
can hold between two events, an event and a time, and two times.

####  2.2.2 TimeML

Deficiencies in TIDES led to the development of TimeML (Sauri et al., 2006),
another markup language for annotating temporal information, originally
designed for news. As shown in Table 1, TimeML contains all Allen’s basic
temporal relations. TimeML does not have Allen’s overlaps and overlapped_by
relations directly, however, these relations can be expressed in the temporal
representation of a TimeML document by combinations of other relations
(Llorens et al., 2015). TimeML adds additional representational facilities.
First, Allen’s equals relation indicates two intervals have the same start and
end time. In contrast, TimeML offers more refined relations: simultaneous
represents two events that happened simultaneously, during represents an event
persists throughout a temporal expression (duration), and identity represents
event coreference relation between two events. Furthermore, TimeML includes
relations for expressing sub-event structure (aspectual relations) and
relations of conditional, hypothetical, or counterfactual nature
(subordinating relations). Because the input to tlex is a TimeML graph, we
give here a detailed exposition of the representational structure of TimeML.

TimeML uses TIMEX3 expressions, which introduce additional attributes and
features to capture more complex temporal expressions accurately. These
features include quantifiers ("quant"), frequencies ("freq"), anchoring for
relative expressions ("anchorTimeID"), and comments for additional
information. While TIMEX3 retains the three basic types of temporal
expressions from TIMEX - dates (DATE), times (TIME), and durations (DURATION)
- it also introduces a new type, "SET," to represent recurring events (e.g.,
twice a week).

TimeML has three different types of links: temporal (tlink), subordinating
(slink), and aspectual (alink). tlinks comprise $14$ different types of
temporal relations between events and times. Figure 1 graphically shows all
types of tlinks in TimeML. The following example represents one of the tlinks,
called is_included. This tlink represents that the event (went) is_included in
(on) the time (Monday). The visual representation of this tlink and the other
examples can be seen in Figure 2. $1$ is the first node of the link, $2$ is
the second node of the link, and $X$ is the TimeML link type.

Figure 2: The visual representation of a generic link of TimeML: node $1$ and
node $2$ represent two intervals, and $X$ represent the TimeML link type
between the two intervals.

. David went1 to the school on Monday2. (is_included)

alinks represent the relation between an aspectual event and its argument
event. There are five types of alinks (shown in Figure 1): initiates,
reinitiates, terminates, culminates, and continues. The following example
shows the aspectual relation between events, where the first event (started)
initiates the second event (study).

. Mike started1 to study2. (initiates)

Note that some alinks and tlinks may have the same temporal constraints (Table
1), but semantically they are different in TimeML. For example, initiates and
begins have the same temporal constraints, however, initiates happen between
an aspectual event and its argument event while begins does not require an
aspectual event.

slinks are used for contexts introducing possible (modal), counterfactual, or
conditional relations between two events, spanning six types: modal, factive,
counter_factive, evidential, negative_evidential, and conditional. The modal
relation introduces a relation to a possible event. In the following example,
the event (buy) is merely a possibility and has not actually happened yet.

. Cindy promised1 him to buy2 some nachos. (modal)

The factive relation marks an entailment of an event’s veracity. On the other
hand, a counter_factive relation marks a presupposition about the event’s non-
veracity. In other words, factive indicates a presupposition as to whether the
event happened in the real world and counter_factive indicates a
presupposition as to whether the event did not happen in the real world. The
following examples demonstrate the difference between these two SLINKs.

. Katy forgot1 that she was2 in Miami last year. (factive)

. Katy forgot1 to buy2 some chocolate. (counter_factive)

evidential relations are introduced by reporting events asserting that the
argument event happened. Similarly, negative_evidential relations are
introduced by reporting events asserting that the argument event did not
happen. The following examples show these two slink types.

. Colin said1 he went2 to the store. (evidential)

. Darius denied1 that he has coronavirus2. (negative_evidential)

Finally, the conditional relation identifies two events linked in a
conditional manner, for example, with a signal such as “if”.

. If Amanda marries1 him, she will be happy2. (conditional)

Language introducing an slinks does not always entail a temporal relation, but
if it does, a tlink representing that relation should be added to the graph as
well. Furthermore, three types of slinks explicitly indicate that the event is
presumed to not have happened in the “real world” of the text. Therefore,
ignoring subordinating relations or treating them as normal temporal relations
gives an incorrect and impaired view of the temporal structure of the text.

Out of the three types of TimeML links, alinks and tlinks represent temporal
information in documents, while slinks indicate non-temporal relations. On the
other hand, slinks and alinks can only connect two events, while tlinks can
relate two events, two times, or an event and a time.

A well-formed TimeML graph will have at most a single tlink and a single alink
relation between two nodes. This is a consequence of the TimeML rule, which
says that between two event instances (or between an event instance and a time
expression), there cannot be two or more tlink or alink types. If there is
both a tlink relation and an alink relation, they must be temporally
consistent (Pustejovsky et al., 2003b, a). As a consequence, TimeML graphs are
atomic temporal graphs, hence a member of the tractable subclass of the
interval algebra (Valdes-Perez, 1986, 1987) (atomic graphs are called
“singleton networks” in these papers). Another way to see this is by combining
the fact that atomic temporal graphs can be equivalently transformed (in
linear time) into their corresponding PA temporal graphs, and that consistency
of PA temporal graphs can be checked in $O(n^{2})$ time (van Beek, 1992).

####  2.2.3 TimeML Annotations

There are a number of manually and automatically annotated TimeML corpora. In
this work, we tested our approach on four manually annotated TimeML corpora:
TimeBank 1.2, the N2 corpus, the ProppLearner corpus, and the NewsReader
MEANTIME corpus, all in English. The number of texts, words, events, temporal
expressions, and relations are listed in Table 2. TimeBank 1.2 is drawn from
various sources such as ABC, CNN, and the Wall Street Journal (Pustejovsky et
al., 2003a). The ProppLearner corpus was developed to enable the machine
learning of Vladimir Propp’s morphology of Russian hero tales and has 18
different layers of syntax and semantics annotated on it, including TimeML
(Finlayson, 2017). Similarly, the N2 corpus is a collection of narratives
relating to Islamic Extremism with 14 layers of annotation, including TimeML
(Finlayson et al., 2014). Finally, the NewsReader MEANTIME corpus is a
semantically annotated corpus of English Wikinews articles (Minard et al.,
2016) (the corpus also includes TimeML annotations of article translations in
Italian, Spanish and Dutch), covering four news topics: “Airbus and Boeing”,
“Apple”, “the Stock market” and “General Motors, Chrysler and Ford.”

Automatic TimeML annotation can be done via temporal information extraction
systems for TimeML temporal expressions, events, and temporal relations
(Verhagen et al., 2005; Bethard, 2013; Chambers et al., 2014; Mirza and
Tonelli, 2016), or via temporal dependency parsers (Zhang and Xue, 2018).
While not perfect, these automatic TimeML annotators attain a reasonable, even
good, level of performance under some conditions. Because our goal in this
paper is to present details of the tlex method for extracting timelines in an
exact manner, we leave as future work the problem of applying our approach on
automatically generated TimeML graphs.

Corpus Name | Texts | Words | Events | TIMEXs | Links | Text Types
---|---|---|---|---|---|---
ProppLearner | 15 | 18,862 | 3,438 | 142 | 2,778 | Russian Hero tales
N2 Corpus | 67 | 28,462 | 2,345 | 349 | 4,854 | Religious Texts, Magazine
MEANTIME | 120 | 13,981 | 2,096 | 525 | 1,717 | WikiNews Articles
TimeBank | 183 | 68,555 | 7,935 | 1,414 | 9,615 | Newswire, Biography, etc.
Total | 385 | 129,860 | 15,814 | 2,430 | 18,964 |
Table 2: Summary of the corpora used in the experiments.

###  2.3 Prior Approaches to Timeline Extraction

The goal of timeline extraction under quantitative (i.e., metric) frameworks
is to produce timelines for temporal networks with metric temporal information
for all times, events, and relations (i.e., numerical durations of nodes and
edges in the temporal graph). Note that a solution for a quantitative
framework does not immediately extend to a solution for qualitative cases such
as Allen’s algebra or TimeML. This is because qualitative frameworks
explicitly allow the use of non-metric information in their temporal graphs;
indeed, most of the temporal information in natural language is non-metrical.

In the field of qualitative spatial and temporal reasoning (QSTR), researchers
have given significant attention to timeline extraction. van Beek (1992)
presented an approach that transformed Allen’s interval algebra temporal
graphs into a point algebra network and solved them using backtracking
techniques. Gereveni and Schubert (1995) built a “timegraph” given a set of
point algebra relations and solved the timegraph using their own algorithm.
Later, Wallgrün et al. (2006) presented the SparQ (Spatial Reasoning done
Qualitatively) tool, which comprises a set of modules to provide different
services for qualitative spatial reasoning, which is a similar problem to
qualitative temporal reasoning. SparQ transforms a quantitative description of
a spatial configuration into a qualitative description, applies the operations
in the calculi to spatial relations, and finally performs computations on
constraint networks. Similarly, Gantner et al. (2008) built the Generic
Qualitative Reasoner (GQR) to solve binary qualitative constraint graphs,
which takes a temporal calculus description and one or more constraint graphs
as input and solves them using path consistency and backtracking. To check the
consistency of large qualitative spatial networks, Sioutis and Condotta (2014)
presented Sarissa, which produces random scale-free-like qualitative spatial
networks using the Barabási-Albert (BA) model and uses a hash table-based
adjacency list to efficiently represent and reason with them. Finally,
Kreutzmann and Wolter (2014) showed how to use AND-OR linear programming (LP)
and mixed integer linear programming (MILP) to solve qualitative graphs, a set
that includes graphs represented in Allen’s algebra.

In the NLP field, researchers have explored different methods for timeline
extraction in general, and from TimeML annotated texts in particular. A
prominent example of general timeline extraction is the news timeline
summarization (TLS) task. Starting from the seminal work of Allan and his
collaborators (Swan and Allan, 2000; Allan et al., 2001), timeline
summarization focuses on finding specific date mentions in texts and
organizing the text or its subpart along a timeline indexed by date. TLS has
attracted much attention in the past two decades; for the latest developments
see (Ghalandari and Ifrim, 2020) and references therein. While this is a
useful task for many purposes, it is much different from (and much more
granular than) the task we set ourselves here, which is organizing all the
events and times mentioned in a text into a (non-metric) timeline.

With regard to approaches that seek to extract timelines from TimeML annotated
texts, we can divide these methods into two categories: (1) ML-based
approaches that start from raw text, or raw text annotated only with events
and time expressions (i.e., no links); and (2) temporal reasoning on fully
TimeML annotated document.

For the first category, researchers build a model to parse documents, predict
TLINKs, and infer the interval-based order. Mani et al. (2006) demonstrated a
machine learning method to annotate events and partially order them using a
qualitative temporal graph generated using Allen’s temporal relations.
However, this model only predicted three relations—before, after, and
simultaneous—and thus excludes large portions of TimeML, and only achieves
roughly 75% ordering accuracy. Do et al. (2012) generated the same three
relations to obtain a full ordering, achieving a similar accuracy of 73%. In
addition to the imperfect performance of these systems, in both cases the
methods only consider intervals, rather than start and end points, and so lose
much detailed temporal information. Finally, Kolomiyets et al. (2012)
presented two models for extracting timelines from qualitative temporal
graphs, one based on shift-reduce parsing, and one based on graph parsing.
Both approaches take a sequence of event words as input and produce a tree
structure. Achieving 70% accuracy, their model generated six temporal
relations—before, after, includes, is_included, identity, overlap—again, only
a subset of the full possible set of temporal relations. Similarly, Zhang and
Xue (2018) built a parser to extract dependency trees, which can easily be
transformed into a timeline. They used LSTM in their pipeline and achieved 76%
accuracy. Later, Ocal and Finlayson (2020) showed that temporal dependency
trees omit temporal information. Using CNNs and LSTMs, Leeuwenberg and Moens
(2020) demonstrated a deep learning model to predict events’ start time-point,
duration, and end time-point. Their model extracts three types of tlinks
between events (before, after, and overlaps), achieving 77% accuracy. And
finally, Mathur et al. (2022) built a temporal parser to extract a temporal
dependency graph and maintain the temporal order of the events using
contextual features such as BERT. They achieved 77% accuracy on four
tlinks—before, after, includes, and overlaps. As can be seen these ML-based
approaches have only been applied to partial TimeML annotations (3–6/25 TimeML
links) with imperfect performance (70–77% accuracy).

In the second category—i.e., temporal reasoning-based methods—Verhagen et al.
(2006) introduced Tango, a TimeML parser tool to parse the TimeML annotated
documents and create a TimeML graph. Using the TIMEX values, Tango displays
the graph in a timeline form, where each section of the timeline contains a
TIMEX and all the events connected to the TIMEX, however, it doesn’t provide
the global order of events. Although Tango checks the consistency of the
TimeML graphs using path consistency, it didn’t report any inconsistencies for
their test corpus (the TimeBank corpus). Similar to Tango, Verhagen (2007)
introduced TBOX, a TimeML parser. TBOX also generates a TimeML graph from a
TimeML annotation, but it further removes the temporal closure links to
display a simplified TimeML graph. TBOX displays each event in a box shape and
places each box based on the temporal relation to present the timeline (e.g.,
if event $A$ is before event $B$, then boxA would be on the left of boxB).
However, this representation is problematic, considering temporal
indeterminacy is already high in TimeML annotations (Verhagen, 2007). Although
these two tools use all 14 types of tlinks, they ignore slinks and alinks.
Therefore, many events would not be correctly displayed in the timeline
structure.

Additionally, Ning et al. (2018) introduced a multi-axis annotation framework
aimed at categorizing intention, opinion, hypothetical, generic, and negation
events into distinct axes to distinguish them from static and recurring
events. This innovative annotation approach led to the development of the
MultiAxis Temporal Relations for Start-points (MATRES) corpus.

Summarizing these approaches for timeline extraction, we see that on the one
hand, QSTR approaches transform Allen’s interval algebra graphs into
constraint graphs and solve them using constraint satisfaction techniques.
Although these approaches provide a solution for solving qualitative temporal
graphs, their methods cannot be applied directly to TimeML graphs because of
subordinating relations, and they also do not detect or represent
indeterminacy, nor do they help with correcting inconsistencies. ML-based
approaches, on the other hand, have been limited by the number of relations
considered and provide inexact solutions, presumably because of the noise
inherent in a statistical solution. Finally, the TimeML parsers do not provide
global orders for all events since they ignore aspectual and subordinating
events.

tlex addresses both of these sets of deficiencies by drawing on both QSTR and
NLP to provide a technique for extracting exact timelines from full TimeML
graphs. Unlike prior approaches, tlex provides a timeline extraction method
using all temporal relations, including aspectual and subordinating relations.
It also exposes indeterminacy in ordering, which is a natural consequence of
the ambiguity of natural language, and also clearly identifies the sources of
inconsistency to enable manual correction. Expanding Ning et al. (2018)’s
comprehensive multi-axis annotation framework, tlex creates a trunk-and-branch
timeline structure that also effectively segregates counter-factive and
negative evidential events from real-life events.

##  3 TLEX Algorithms

###  3.1 Overview of our approach

####  3.1.1 Problem statement

Recall that our task is to, by taking all possible temporal relations
(including aspectual and subordination relations) into consideration, extract
from a TimeML annotated text a complete set of timelines that are consistent
with the TimeML temporal graph, identify which portions of the timelines are
indeterminate, and organize those timelines into a trunk-and-branch structure.

Without loss of generality, we may view the input TimeML temporal graph to
tlex as a connected555Because if the TimeML temporal graph is not connected,
then we can simply run tlex on each of its connected components separately.,
_directed_ graph $G_{TM}=(V_{TM},E_{TM})$, where the vertex set $V_{TM}$ are
events and time expressions, and there is a directed edge from vertex $u$ to
vertex $v$ if there is a TimeML link from $u$ to $v$ (note that there can be
more than one link, hence multiple relations corresponding to a single edge of
$G$). That is, $E_{TM}=\\{(u,v):u,v\in V_{TM}\text{ and there is a {\sc
tlink}, {\sc slink}, or {\sc alink} from $u$ to $v$}\\}$.666A simple way to
implement this would be to assign a $10$-bit vector for each edge as follows.
First use $\bf{0}$ vector to denote no relation exists for each of the three
types of links. The type of tlink relation of an edge can thus be represented
with $\lceil\log_{2}(14+1)\rceil=4$ bits; similarly, slink relation needs
$\lceil\log_{2}(5+1)\rceil=3$ bits and alink relation needs
$\lceil\log_{2}(6+1)\rceil=3$ bits. Let $n=|V_{TM}|$ be the number of
intervals in the input TimeML temporal graph and $m=|E_{TM}|$ be the number of
edges of $G_{TM}$. As $G_{TM}$ is connected, $m\geq n-1$; and since there can
be at most one link of each type between an (ordered) pair of temporal
intervals, the number of links in the TimeML temporal graph is at most $3m$.

####  3.1.2 Structure of the algorithm

tlex consists of the following five steps:

  1. 1.

Partitioning, in which the input TimeML temporal graph is partitioned into
subgraphs connected with only temporal and aspectual links;

  2. 2.

Transforming, in which each TimeML temporal subgraph is transformed into a PA
constraint subgraph with time-points as vertices and basic temporal relations
($<$, $=$) as edge labels;

  3. 3.

Consistency Checking, in which the consistency of each PA constraint subgraph
is checked, a maximal list of inconsistent cycles is output for manual
correction and only consistent PA constraint subgraphs are passed on to the
next step;

  4. 4.

Timeline Generation, in which the _minimum_ timeline for all the time-points
in each PA constraint subgraph is generated;

  5. 5.

Indeterminacy Detection, in which each pair of time-points in the generated
timeline can be checked whether there is any ordering indeterminacy777More
precisely, by _indeterminacy_ , we mean the possibility of generating some
other timeline in which the ordering of the two time-points is reversed.
between them.

####  3.1.3 A running example

In the following sections we provide detailed descriptions and analysis of
each step, using the following text as a running example:

. After working1 in the morning2 John came back3 home. He wished4 that he
didn’t go5 to work, so he could be happy6. Later, his phone rang7 and he
answered8 it. As soon as he picked up9, Paul started10 complaining11. He was
quickly bored12, but realized13 that if he hung up14, Paul would be mad15 for
the entire weekend16. So he continued17 to listen18. Then he remembered19 he
ignored20 Paul’s text in the morning2.

In this example, each event is underlined and given a numerical subscript for
reference. One thing notable about this example text is that events 14 and 15
did not happen in the “real world” of the story: because John did not hang
up14 the phone, Paul didn’t get mad15. These two events are related to the
“real world” timeline by subordinating links and should be isolated onto their
own “subordinated” timeline.

We informally define a “main” or “real world” timeline as a timeline that
contains the events and times that actually happen in the “world” described in
the text. Similarly, we informally define “subordinated” timelines as
containing events that did not occur in the world described in the text. As
noted, in the example text, the events hang up14 and would be mad15 belong to
a subordinated timeline. It is possible that there are multiple main timelines
in a text; we treat this possibility formally in §4.3.

####  3.1.4 Depth First Search (DFS)

We will need the standard DFS (depth first search) algorithm to explore a
directed graph and detect cycles in the graph. For completeness, we provide
the notation and the pseudo-code of the DFS version presented in Section 20.3
of Cormen et al. (2022), omitting the $time$ field as we do not use it.

Specifically, on an input directed graph $G=(V,E)$ stored as an adjacency
list, DFS initially colors all vertices as white. When DFS begins to explore
the neighborhood of a vertex $u$ (by recursively calling DFS-Visit on each
vertex $v$ which is in $u$’s adjacency list $G.Adj[u]$ and whose color is
still white), it changes $u$’s color to gray. When DFS finishes examining
$u$’s neighbors, it changes $u$’s color to black and the color of $u$ will
never be changed again after that. Apart from color, each vertex also has a
field $\pi$, which is used to store its parent node in the DFS forest
constructed in the process of graph exploration. It is known that DFS runs in
time linear time, namely $O(n+m)$ where $n=|V|$ is the number of vertices and
$m=|E|$ is the number of edges of the graph $G$.

Algorithm 1  DFS$(G)$

1:directed graph $G=(V,E)$

2:a DFS forest

3:for all $v\in V(G)$ do

4: $u.color=\textsc{white}$

5: $u.\pi=\textsc{nil}$

6:for all $v\in V(G)$ do

7: if $u.color==\textsc{white}$ then

8: DFS-Visit$(G,u)$ DFS-Visit$(G,u)$

9:$u.color=\textsc{Gray}$

10:for all $v\in G.Adj[u]$ do

11: if $v.color==\textsc{white}$ then

12: $v.\pi=u$

13: DFS-Visit$(G,v)$

14:$u.color=\textsc{black}$

###  3.2 Partitioning

In this step, tlex partitions the TimeML graph into subgraphs that are
connected only with temporal and aspectual relations. The reason is that
temporal and aspectual relations represent temporal information about the
text, while subordinating relations do not.

To do this, we first transform the input graph $G_{TM}=(V_{TM},E_{TM})$ into
an _undirected_ graph $G^{\prime}_{TM}=(V_{TM},E^{\prime}_{TM})$ by keeping
the same vertex set and adding an (undirected) edge $(u,v)$ between two
vertices $u$ and $v$ if there is a temporal or aspectual relation from $u$ to
$v$, or a temporal or aspectual relation from $v$ to $u$. That is, we ignore
all slink relations and view tlink and alink relations as undirected edges.
This can clearly be done in $O(n+m)$ time. Next, we run DFS as illustrated in
Algorithm 1 on $G^{\prime}_{TM}=(V_{TM},E^{\prime}_{TM})$ and partition it
into connected subgraphs. Since the transformed graph
$G^{\prime}_{TM}=(V_{TM},E^{\prime}_{TM})$ has
$|E^{\prime}_{TM}|\leq|E^{\prime}_{TM}|$, the DFS runs in $O(n+m)$ and hence
the total running time of Partitioning is also $O(n+m)$. We denote the
resulting subgraphs as $G^{(1)}_{TM},\ldots,G^{(k)}_{TM}$.

Figure 3 illustrates Partitioning on the TimeML graph corresponding to Example
3.1.3. Subgraphs are separated with dashed lines. Since there are no temporal
or aspectual links between event pairs 5 & 6 and 14, 15 & 16 with the rest of
the graph (but the graph is otherwise connected), tlex partitions the graph
into three temporally connected subgraphs: the main, or “real world” subgraph
(1-2-3-4-7-8-9-10-11-12-13-17-18-19-20) and the subordinated subgraphs (5-6 &
14-15-16). tlex will subsequently extract a separate timeline from each of
these subgraphs.

After the partitioning, tlex stores the _connecting points_ between the main
subgraphs and subordinated subgraphs (these points can be easily found by
scanning the subordinating links: if a subordinating link $(u,v)$ connecting
one vertex from a main subgraph and one vertex from a subordinated subgraph,
then both vertices $u$ and $v$ are connecting points). Connecting points will
be used later to build the trunk-and-branch timeline. The connecting points in
Example 3.1.3 are 4 & 5 and 13 & 14.

Figure 3: Visualization of the TimeML graph from the example. Numbers
correspond to the events in the text, and arrows correspond to the temporal,
aspectual, or subordinating links. The two temporally and aspectually
connected subgraphs are separated by dashed lines, and links on the “real
world” timeline are bolded.

###  3.3 Transforming

In TimeML, DATE, DURATION, and SET temporal expressions are regarded as
temporal intervals, with starting and ending time points.888Note that
reinitiates occurs between a continuous event and a reinitiating trigger word
(such as resuming or renewing). If the event is not continuous, then there
will be two different event instances instead of one, and the second event
instance will be initiated by the trigger word. TIME temporal expressions
represent a specific moment in time, such as 9:46 pm or 1 am. Unlike
intervals, they don’t have a duration and simply pinpoint a single time-point
in PA (Barták et al., 2014). We transform each temporal _intervals_ and time
stamps of TimeML subgraph $G^{(i)}_{TM}$ into a point algebra (PA) constraint
graph $G^{(i)}_{PA}=(V^{(i)}_{PA},E^{(i)}_{PA})$, for every $i=1,\ldots,k$.

Let $G^{(i)}_{TM}=(V^{(i)}_{TM},E^{(i)}_{TM})$ be any of the interval TimeML
subgraphs. Note that we still view $G^{(i)}_{TM}$ as a _directed_ graph
following the same definition as the original graph $G_{TM}$; that is, there
is a directed edge from vertex $u$ to vertex $v$ in $G^{(i)}_{TM}$ if and only
if there is a tlink relation or an alink relation between them.

Recall that each vertex $v\in V^{(i)}$ actually represents a temporal interval
$I_{v}$, so we first replace each interval $v$ with two time-points, the start
time-point $t^{-}_{v}$ and the end time-point $t^{+}_{v}$ of the interval
$I_{v}$. More formally, we let

$V^{(i)}_{PA}=\\{t^{-}_{v}:v\in V^{(i)}_{TM}\\}\cup\\{t^{+}_{v}:v\in
V^{(i)}_{TM}\\}.$

Now we construct the edges of $G^{(i)}_{PA}$ (i.e., basic PA constraints) as
follows. First, we add the constraint $t^{-}_{v}<t^{+}_{v}$ for every $v\in
V^{(i)}$. Using the fact that each tlink or alink can be represented as a
simple conjunction of the basic temporal constraints less than (<) and equals
(=) as shown in Table 1, we next, for each directed edge in $E^{(i)}_{TM}$,
add its corresponding basic PA constraints to $E^{(i)}_{PA}$. More formally,
if we use $\phi(u,v,t^{+}_{u},t^{-}_{u},t^{+}_{v},t^{-}_{v})$ to denote the
set of PA constraints, as specified in Table 1, between
$\\{t^{+}_{u},t^{-}_{u}\\}$ and $\\{t^{+}_{v},t^{-}_{v}\\}$ which are imposed
by the TimeML constraint of an edge $(u,v)$ in $G^{(i)}_{PA}$, then

$E^{(i)}_{PA}=\left(\cup_{v\in
V^{(i)}_{TM}}\\{t^{-}_{v}<t^{+}_{v}\\}\right)\bigcup\left(\cup_{(u,v)\in
E^{(i)}_{TM}}\phi(u,v,t^{+}_{u},t^{-}_{u},t^{+}_{v},t^{-}_{v})\right).$

It is easy to check that the blowup of PA constraint graph size is at most a
constant factor, namely $|V^{(i)}_{PA}|=2|V^{(i)}_{TM}|$ and
$|E^{(i)}_{PA}|\leq|V^{(i)}_{TM}|+2|E^{(i)}_{TM}|$. In the following we write

$n_{i}:=|V^{(i)}_{PA}|$

for the number of vertices in the $i^{\text{th}}$ PA constraint subgraph and

$m_{i}:=|E^{(i)}_{PA}|$

for the number of edges in the $i^{\text{th}}$ PA constraint subgraph. Note
that $\sum_{i=1}^{k}n_{i}=2n$ and $\sum_{i=1}^{k}m_{i}\leq n+2m$. It follows
that Transforming takes linear time $O(n+m)$ to compute. While certain
temporal details like verb tense and specific linguistic signals are lost
during the transformation of the TimeML graph to the PA graph, the information
pertaining to the global order of events and times remains intact.

Figure 4 illustrates the transformed PA constraint graph from the TimeML
temporal graph shown in Figure 3.

Figure 4: The three PA constraint subgraphs transformed from the three
temporally and aspectually connected subgraphs in Figure 3. These are produced
by replacing each node $I$ with its start and end time-points $I^{-}$ and
$I^{+}$, and replacing each temporal or aspectual link with the set of basic
temporal relations shown in Table 1.

###  3.4 Consistency Checking

A _timeline_ for a PA constraint graph $G_{PA}=(V_{PA},E_{PA})$ is a function
$L$ that maps each time-point in $V_{PA}$ to a (not necessarily unique) point
on the real axis such that all time-point constraints imposed by $E_{PA}$ are
satisfied. A PA constraint graph $G_{PA}=(V_{PA},E_{PA})$ is _consistent_ if
there exists a timeline $L$ for $G$. Therefore we need to check the
consistency of each PA constraint subgraph before passing it on for timeline
generation.

It was shown by van Beek (1992) that a PA constraint graph is consistent if
and only if it does not have any of the following three types of inconsistent
cycles.

######  Definition 1 (Inconsistent Cycle).

An inconsistent cycle is a cycle in a PA constraint graph with one of the
following types (for simplicity of notation, we use “$\neq$” as shorthand for
the relation “$<$” or “$>$” and use “$\leq$” as shorthand for the relation
“$=$” or “$<$”) :

  1. (i)

$v=...=w\neq v$;

  2. (ii)

$v\leq...\leq w\leq...\leq v\neq w$;

  3. (iii)

$v<...<w<...<v$, where all but one of the $<$ can be $\leq$ or $=$ (Note that
this case also covers the case of self-loops, $v<v$).

An example of an inconsistent cycle is shown in Figure 5.

Figure 5: Example of an inconsistent cycle generated by A before B and B
before A.

In the third step of tlex, namely Consistency Checking, given a PA constraint
subgraph $G^{(i)}_{PA}=(V^{(i)}_{PA},E^{(i)}_{PA})$, our task is to check if
$G^{(i)}_{PA}$ is consistent; moreover if $G^{(i)}_{PA}$ is inconsistent,
output a _Maximal List of Inconsistent Cycles_ (MLIC) which includes the set
of all inconsistent cycles detected in our checking procedure. This list of
TimeML links that correspond to these points can then be provided to human
annotators for manual corrections. Although there has been some research in
the field of qualitative spatial reasoning focused on automatically correcting
inconsistencies in point algebra constraint graphs in a minimum or approximate
manner (Iwata and Yoshida, 2013; Condotta et al., 2016), these approaches
cannot be applied to TimeML graphs. Inconsistencies in TimeML graphs usually
come from incorrect or incomplete annotations; more rarely, there may be
fundamental inconsistencies in the meaning of the language. Therefore, errors
need to be fixed by reference to the original text. It is possible that one
could develop other knowledge- or inference-based methods for automatically
correcting these inconsistencies, but we will leave the exploration of this
for future work. This means that any inconsistencies discovered by tlex need
to be manually corrected before proceeding. We discuss more specific cases of
inconsistencies in selected corpora in Section 4.

Consistency Checking comprises the following three parts.

####  3.4.1 Merging equal time-points into “compound” time-points

In this part, we merge time-points that are inter-connected by equals (=)
relations. Specifically, we keep only the $=$ relations in the PA constraint
subgraph and view it as an _undirected_ graph. We then run DFS on the modified
graph to partition the vertices in $V^{(i)}_{PA}$ into connected components
$V_{1},\ldots,V_{\ell}$ (Note that some $V_{i}$ may contain a single vertex;
indeed that should be the case for most $V_{i}$’s when the PA constraint graph
is generated from a real-world text corpus). Time-points in each $V_{i}$ are
inter-connected by $=$ relations and hence they should be equal to each other.
We call each such $V_{i}$ a “compound” time-point. Since running DFS on (a
subgraph of) each PA constraint subgraph takes time at most linear in its
size, the total running time for processing all PA constraint subgraphs takes
$O(m+n)$ time.

In the example, PA constraint graph in Figure 4, $8^{-}$ and $9^{-}$ will be
merged into one “compound” time-point, $8^{+},9^{+}$ and $11^{-}$ will be
merged into another “compound” time-point, and the remaining time-points will
be singleton “compound” time-points.

####  3.4.2 Building “compound” PA constraint graph, detecting type (i) and
type (ii) inconsistency

We now build a “compound” PA constraint graph
$\tilde{G}^{(i)}_{PA}=(\tilde{V}^{(i)}_{PA},\tilde{E}^{(i)}_{PA})$: the vertex
set $\tilde{V}^{(i)}_{PA}$ is just the set of “compound” time-points created
in the previous part, and the labels of the edges will be of less than (<)
relation only and can be generated by scanning the set of less than (<)
labeled edges in $E^{(i)}_{PA}$. More specifically, we first associate a new
field “compound index” (an integer between $1$ and $\ell$) to each vertex in
$V^{(i)}_{PA}$, indicating to which “compound’ time-point the corresponding
time point belongs. We then create an $\ell\times\ell$ Boolean-valued table
$T$ whose $(i,j)$-entry stores whether “compound” time-point $i$ is less than
“compound” time-point $j$. We now go through all less than (<) labeled edges
in $E^{(i)}_{PA}$ and update the entries of $T$ accordingly. During this
process, we also detect inconsistency cycles as follows:

detecting type (i) inconsistency:

If there is a constraint $u<v$ and $u,v$ both belong to the same “compound”
time-point, then a type (i) inconsistency cycle is found, and we add all time-
points in this “compound” time-point to the MLIC;

detecting type (ii) inconsistency:

For every constraint $u<v$ where $u$ belongs to “compound” time-point $i$ and
$v$ belongs to “compound” time-point $j$, we update the $(i,j)$-entry of $T$
to TRUE. We then check the $(j,i)$-entry of $T$ and a type (ii) inconsistency
cycle is detected if that entry is also TRUE. If so, we add all time-points in
both “compound” time-point $i$ and “compound” time-point $j$ to the MLIC.

Note that now the “compound” PA constraint graph has $\ell\leq n_{i}$
vertices, at most $m_{i}$ directed edges and all edges are label with less
than (<) relations. As we need to build the table $T$, the running time is
$O(n^{2}+m)$.

####  3.4.3 Cycle-finding in “compound” PA constraint graph—detecting type
(iii) inconsistency

To detect type (iii) inconsistency in
$\tilde{G}^{(i)}_{PA}=(\tilde{V}^{(i)}_{PA},\tilde{E}^{(i)}_{PA})$, we apply
the well-known cycle-detection method of DFS. Run the DFS described in
Algorithm 1 on $\tilde{G}^{(i)}_{PA}$ with the following slight modifications:
if when vertex $u$ explores its neighboring vertices in Line 9 and finds that
$v$’s color is gray, then a cycle is detected. Proof of the correctness of
this method is well-known, but for completeness we provide a sketch here. Let
$v_{1}<v_{2}<\cdots<v_{p}<v_{1}$ be a cycle in $\tilde{G}^{(i)}_{PA}$ and
without loss of generality $v_{1}$ is the first vertex to be discovered by
DFS. By the White-path Theorem, (Cormen et al., 2022) Theorem 20.9, $v_{p}$ is
a descendant of $v_{1}$ in the DFS forest generated by the algorithm; it
follows that when $v_{p}$ is discovered in Line 12, the color of $v_{1}$ is
still gray, hence the cycle will surely be detected. On the other hand, if a
vertex $u$ finds that $v$’s color is gray when exploring its neighbors, then
$v$ is an ancestor of $u$, meaning that there is a directed path from $v$ to
$u$. But $v$ is a neighbor of $u$ implies there is an edge from $u$ to $v$.
Therefore there must be a cycle containing both $u$ and $v$.

To detect all possible type (iii) inconsistency cycles, each time a cycle is
detected we remove edge $(u,v)$ from $\tilde{G}^{(i)}_{PA}$ to break the
cycle, add the cycle to the MLIC (the cycle can be found by tracing back
recursively the parent vertex $u.\pi$ starting from $u$ until we reach vertex
$v$), and keep running the DFS algorithm till it finishes. The running time of
this part is $O(m+n)$

##### Summary of Consistency Checking.

From our analysis in each of the three parts, the overall running time of
Consistency Checking is clearly $O(m+n^{2})$. Note that, if the algorithm does
not detect any inconsistency in the “compound” PA constraint subgraph
$\tilde{G}^{(i)}_{PA}$ and passes it on to next step, then the “compound” PA
constraint subgraph satisfies

  1. 1.

$\tilde{G}^{(i)}_{PA}$ is a directed acyclic graph (DAG);

  2. 2.

All the constraints are less than (<) relations; that is, if $(u,v)$ is an
edge in $\tilde{G}^{(i)}_{PA}$ then for any timeline $L$ satisfying
$\tilde{G}^{(i)}_{PA}$, $L(u)<L(v)$.

###  3.5 Timeline Generation

Figure 6: A TimeML graph with an indeterminacy. While the order between
interval $I_{4}$ and interval $I_{5}$ is fixed, the relative order between
interval $I_{2}$ and interval $I_{3}$ is indeterminate.

####  3.5.1 Normal Form Timeline

The two properties listed at the end of last section of the “compound” PA
constraint subgraph allow ordering _linearly_ , namely topological sort, all
the time-points involved. Recall that a _topological sort_ of a directed
acyclic graph $G=(V,E)$ is a linear ordering of all its vertices such that if
$G$ contains an edge $(u,v)$, then $u$ appears before $v$ in the ordering.
However, our goal in Timeline Generation is slightly different: for every
“compound” PA constraint subgraph $\tilde{G}^{(i)}_{PA}$, we want to generate
a _shortest_ timeline for time-points in $\tilde{G}^{(i)}_{PA}$, for which we
provide a more formal definition now. We prioritize generating the shortest
timeline among potentially multiple solutions to establish a reference point
for subsequent indeterminacy calculations. This allows for an equitable
distribution of indeterminacy scores across all timeline segments, as detailed
in § 3.6. To keep notation simple, in the rest of this section we use a
general PA constraint graph $G=(V,E)$ instead of $\tilde{G}^{(i)}_{PA}$ as the
input to Timeline Generation.

First, in order to make notation simple and eliminate unnecessary ambiguities,
we require the values of a timeline to be positive integers, hence the notion
of _normal form timelines_. Let $\mathbb{N}=\\{1,2,\ldots\\}$ denote the set
of natural numbers.

######  Definition 2 (Timeline and normal form timeline).

Let $G=(V,E)$ be a PA constraint graph. A function $L:V\to\mathbb{R}$, which
maps every time-point in $V$ to a real number, is called a _timeline_ of
$V(G)$ if all the temporal constraints imposed by $E$ are satisfied. A
timeline is said to be in _normal form_ if the range of the timeline $L$ is
further restricted to be $\mathbb{N}$. The _length_ of a normal form timeline
is the maximum value of the timeline $\ell(L)=\max_{u\in V}L(u)$. A timeline
$L$ is called a _minimal normal form timeline_ of $G$ if for any normal form
timeline $L^{\prime}$ of $V(G)$, $\ell(L)\leq\ell(L^{\prime})$. Finally, a
timeline $L$ is called a _minimum normal form timeline_ if for any normal form
timeline $L^{\prime}$ of $V(G)$ and every vertex $u$ in $V$, $L(u)\leq
L^{\prime}(u)$.

It follows immediately from the definitions that if a timeline $L$ is a
minimum normal form timeline then it is also a minimal normal form timeline.
However, the converse is in general not true. The motivation behind our
definitions is the following. It is possible that there are multiple normal
form timelines of a PA constraint graph that all have the minimum possible
length. In order to eliminate such ambiguity, we further require the timeline
should map every time-point to its minimum possible value in any consistent
timeline. Indeed, one can show that for any PA constraint graph $G$, the
minimum normal form timeline for $G$ is unique999The uniqueness follows by
inspecting the Greedy Kahn’s algorithm (Algorithm 2) and proving the unique
optimality of its output timeline by an induction on time-points that are
added to set $S$ at iteration $t$. and hence it is justified to call a
timeline _the_ minimum normal form timeline for $G$.

Consider the example shown in Figure 6, one possible normal form timeline
(after transforming the original Allen algebra on temporal intervals into PA
on time-points) $L_{1}$ is to map interval $I_{1}$ to $[1,2]$, interval
$I_{2}$ to $[3,4]$, interval $I_{3}$ to $[5,6]$, interval $I_{4}$ to $[7,8]$,
and interval $I_{5}$ to $[9,10]$, with $\ell(L_{1})=10$. Another normal form
timeline $L_{2}$, as shown in Figure 7, maps interval $I_{1}$ to $[1,2]$, both
interval $I_{2}$ and interval $I_{3}$ to $[3,4]$, interval $I_{4}$ to $[5,6]$,
and interval $I_{5}$ to $[7,8]$, with $\ell(L_{2})=8$. It is not hard to be
convinced that $L_{2}$ is the minimum normal form timeline for the original
TimeML graph.

Figure 7: The minimum timeline extracted from the TimeML graph in Figure 6,
with the indeterminate section highlighted.

tlex assumes, in the absence of additional information, that the minimum
normal form timeline is the best.

####  3.5.2 Minimum normal form timeline generation algorithm

##### Kahn’s topological sort algorithm.

We first review the classic Kahn’s algorithm (Kahn, 1962) for topological sort
as it is the basis of our minimum normal form timeline generation algorithm.
It is helpful to view topological sorting vertices in $V$ as a scheduling
problem (for example, taking courses to complete an undergraduate degree), and
think edges in $E$ as scheduling constraints (if there is an edge from $u$ to
$v$, it means course $u$ is a prerequisite for course $v$). Kahn’s topological
sort algorithm for an acyclic directed graph (DAG) $G=(V,E)$ is to repeatedly
find a vertex of in-degree $0$, output it, and remove it and all of its
outgoing edges from the graph. The key observation of the algorithm is that,
as long as the in-degree of a vertex becomes $0$, it is free, and we can
safely schedule it. Once it is scheduled, the constraints it imposes on other
vertices can be removed, and this potentially frees more vertices to schedule.
The correctness of the algorithm follows from the fact that there always
exists some vertex of in-degree $0$ in a DAG.101010To see this, suppose this
is not the case. Then every vertex has at least one incoming edge. Now
starting from any vertex $u$ of $G$, repeatedly trace along (in the opposite
direction) any of its incoming edges. Since every vertex has at least one
incoming edge, this process will keep running. But graph $G$ is finite,
therefore the path of this process must eventually visit some vertex it has
visited before. That is, there must exist a cycle in this path. Reversing the
direction of each edge in this path gives rise to a cycle in the original
graph $G$, thus a contradiction. Note that removing a vertex of in-degree $0$
and deleting all its outgoing edges from a DAG can never create new cycles;
therefore, the algorithm will proceed until all vertices are put in a
topological ordering. The running time of Kahn’s algorithm is $O(m+n)$ by the
following analysis. First, we maintain a queue which is set to be empty
initially for the vertices of in-degree $0$. Second, in the preprocessing
stage, by scanning all edges in $E$, we can compute the in-degree of every
vertex, and place all in-degree $0$ vertices in the queue; this takes $O(m+n)$
time. Last, after removing a vertex $u$ of in-degree $0$ from the queue, we go
through $u$’s outgoing edges, delete them from $E$, and update the in-degrees
of $u$’s out-neighbors, and insert any vertex into the queue if its in-degree
becomes $0$. Note that we need to process each edge only once and process each
vertex $O(1)$ times in the whole algorithm, so this part also takes $O(m+n)$
time.

##### Greedy Kahn’s algorithm for minimum normal timeline

Note that the Kahn’s algorithm described above already provides a normal form
timeline for time-points in $V$. What we do next is to slightly modify the
algorithm so that it outputs the minimum normal form timeline.

Since a normal form timeline can only schedule time-points at $t=1,2,\ldots$,
we partition our timeline construction into stages accordingly: at stage $i$,
the algorithm determines which time-points the timeline $L$ should map to
value $i$. A simple idea to construct a _minimum_ normal form time is,
therefore to _greedily_ schedule as many time-points as allowed by the PA
constraint graph. What is the maximal set of time-points that can be scheduled
first, i.e. mapped to value $1$? Clearly, since all time-points with in-degree
$0$ do not have any constraint on them, thus can all be mapped to value $1$.
Following the idea of Kahn’s algorithm, after mapping these time-points to
$1$, we delete their out-going edges (this will create some new time-points of
in-degree $0$ as argued in the preceding paragraph) and map all new in-degree
$0$ time-points to value $2$. We keep repeating this process until all time-
points have been scheduled.

Algorithm 2  Greedy Kahn’s Algorithm

1:A consistent PA constraint graph $G=(V,E)$

2:A minimum normal form timeline $L:V\to\mathbb{N}$

3:$t=0$

4:for all $v\in V(G)$ do

5: $d_{in}(v)=0$

6:$S=\emptyset$

7:for all $(u,v)\in E(G)$ do

8: $d_{in}(v)=d_{in}(v)+1$ $\triangleright$ compute the in-degree of every
time-point

9:while $V\neq\emptyset$ do

10: $t=t+1$

11: $S=\\{u\in V:d_{in}(u)=0\\}$ $\triangleright$ set $S$ contains all
currently “free” time-points

12: for all $u\in S$ do

13: remove vertex $u$ from $V$

14: $L(u)=t$ $\triangleright$ greedily schedule all time-points that are
“free”

15: delete all outgoing edges of $u$ $\triangleright$ remove all constraints
$u$ imposes on other time-points

16: remove $u$ from $S$

The pseudo-code of our greedy Kahn’s algorithm is listed in Algorithm 2. It is
easy to see, following the same argument as that of the original Kahn’s
algorithm, the running time of Greedy Kahn’s algorithm is $O(m+n)$. The
correctness of the algorithm follows from the following lemma.

######  Lemma 1.

For any consistent PA constraint graph $G=(V,E)$, Greedy Kahn’s Algorithm
generates the minimum normal form timeline for $G$.

###### Proof.

Let $L$ be the normal form timeline generated by Greedy Kahn’s Algorithm and
let $L^{\prime}$ be any other normal form timeline. We claim that for any
$u\in V$, $L(u)\leq L^{\prime}(u)$, hence by definition $L$ is the minimum
normal form timeline.

Note that Greedy Kahn’s Algorithm partitions the time-points in $V$ into
$\ell$ disjoint sets, $V=\dot{\bigcup}_{i=1}^{\ell}S_{i}$, where
$\dot{\bigcup}$ stands for disjoint set union and $S_{i}:=\\{u\in V:L(u)=i\\}$
for every $1\leq i\leq\ell$. We prove the claim by induction on the index
number $i$ of $\\{S_{i}\\}$ to which a time-point belongs. The claim is
certainly true for every time-point in $S_{1}$. Now for the inductive step,
suppose the claim is true for all time-points in $S_{1}\cup\cdots\cup S_{k}$.
That is, any other timeline $L^{\prime}$ must have $L^{\prime}(u)\geq L(u)$
for every time-point $u$ in $S_{1}\cup\cdots\cup S_{k}$. Let $v$ be a time-
point in $S_{k+1}$. Why can not $v$ be in $S_{k}$? Because there must exist
another (or more) time-point $w$ such that $(w,v)\in E$ and $w\in S_{k}$. So
if $L^{\prime}$ satisfies that $L^{\prime}(v)=k^{\prime}\leq k$, then we must
also have $L^{\prime}(w)<k^{\prime}\leq k=L(w)$, a contradiction. This
completes the inductive step of the proof and hence the proof of the lemma. ∎

Note that van Beek (1992) developed an efficient algorithm that finds a
consistent scenario (i.e. timeline) for a PA graph by first decomposing the
original graph into strongly connected components (SCCs) and then applying
topological sort on the simplified PA graph. However, our application of the
greedy Kahn’s algorithm in solving PA graphs seems to be new.

The timeline for the running example is shown in Figure 8. As before, there
are two temporally and aspectually connected subgraphs, where the connection
between them (the gray bar) represents the factive subordinating link. As can
be seen, this is a trunk-and-branch multi-timeline structure, where the trunk
is (in this case) the “main” timeline and the branch is the subordinated
timeline.

As we have noted, one major advantage of tlex is its ability to properly
handle subordinating relations. Prior approaches to timeline extraction
ignored subordinating relations. If they were alternatively treated as some
sort of temporal relation, machine-learning-based techniques e.g.,(Verhagen et
al., 2005; Bethard, 2013; Mirza and Tonelli, 2016) would likely insert events
8 and 9 between or near time-points $13^{-}$ and $13^{+}$. That would indicate
events 14 and 15 happened after events 1–12 but before events 17–20, while in
the story world, these events did not occur at all. This is clearly incorrect.

Figure 8: Visualization of the timeline extracted from Figure 4. The three
subgraphs are arranged into a main timeline and subordinated timelines
connected by a grey branch. The indeterminate sections (20 & 1) are
highlighted.

###  3.6 Indeterminacy Detection

In most cases, TimeML graphs lack enough information to uniquely specify the
full ordering; a simple example is shown in Figure 6. For that TimeML graph,
only the orderings among the first event and the last two events in the
timeline are uniquely determined; namely $1^{-}$<$1^{+}$<2 and
3<$4^{-}$<$4^{+}$<$5^{-}$<$5^{+}$. On the other hand, the ordering between
events 2 and event 3 is indeterminate. In fact, there are 13 different
possible scenarios, as shown in Figure 9.

Figure 9: All possible solutions for the graph shown in Figure 6, with
indeterminate orderings highlighted.

As another example, consider the following two events in Example 3.1.3: John
worked in the morning and John ignored the text in the morning. Both events
happened in the morning, however, we do not have enough information to
determine these two events’ order. It is possible he ignored the text before
he started working and it is possible that he ignored it while he was working.
Using the DFS algorithm to be developed in Lemma 2, we can highlight the
temporal indeterminacy as shown in Figure 8.

Therefore, in general, we would like to know whether there is any
indeterminacy between two time-points in a timeline. Specifically, for any two
time-points $u$ and $v$ for which $u<v$ in a given minimum normal form
timeline111111We only need to check the case that one time-point is in front
of another time-point, since if these two time-points are mapped to the same
time $t$ in the minimum normal timeline $L$, then the problem has a trivial
solution. To see this, consider the following two possibilities. First, $u$
and $v$ belong to the same “compound” time-point. This means that there is an
equality constraint between them, therefore these two time-points must always
be mapped to the same time in any consistent timeline. Second, $u$ and $v$ do
not belong to the same “compound” time-point. Since they are mapped to the
same time $t$ in the minimum normal timeline, there does not exist any (direct
or indirect) constraint between $u$ and $v$. Hence we can construct a timeline
in which $u<v$ and another timeline in which $v<u$.  output by Algorithm 2, is
there another timeline in which $u=v$ or $v<u$? As part of tlex, we have an
efficient subroutine to check this.

######  Lemma 2.

Let $L$ be the minimum normal form timeline output by Algorithm 2 in Step 4 of
tlex, and let $u$ and $v$ be two time-points in $L$ with $u<v$. Then there is
an algorithm with running time $O(m+n)$ which checks whether there is another
consistent timeline in which $u=v$ or $v<u$.

###### Proof.

Observe that there exists a timeline $L^{\prime}$ in which $v=u$ or $v<u$ if
and only if there is no directed path from $u$ to $v$ in the PA constraint
graph, as otherwise, $u$ must precede $v$ in any consistent timeline. But such
a fact can be checked by running the DFS algorithm depicted in Algorithm 1
starting from vertex $u$. Note that the difference between our current
algorithm and Algorithm 1 is that here we only run DFS-Visit$(G,u)$ (instead
of exhausting all vertices in the graph) and terminate once the the DFS tree
rooted at $u$ is completely generated. If the DFS tree does not contain $v$,
then there is no such path and there are other consistent timelines in which
$u$ and $v$ mapped to the same time or $v$ precedes $u$. Clearly, such a check
takes at most the running time of the DFS algorithm, which is $O(m+n)$. ∎

Note that, in the worst case that we perform such indeterminacy checking for
all pairs of time-points, the total running time of Step 5 of tlex is at most
$\frac{n(n-1)}{2}\cdot O(m+n)=O(mn^{2}+n^{3})$.

###  3.7 End-to-End Main Theorem

Informally, we call a timeline the “main” timeline if it contains events and
times that actually happen in the “world” described in the text. Because we do
not currently have an automatic way of identifying main timelines, we will
rely on information external to tlex to identify the main timelines. For this,
it is sufficient for a person to identify at least one event or time that
occurs on every disjoint main timeline for the text.

Before stating our main theorem, we need several definitions.

######  Definition 3 (Trunk-and-Branch Timeline).

Let $G_{TM}=(V_{TM},E_{TM})$ be a consistent TimeML graph with temporally and
aspectually connected subgraphs $\\{G^{(1)}_{TM},\ldots,G^{(k)}_{TM}\\}$ and
corresponding timelines $T_{L}=\\{L_{1},\ldots,L_{k}\\}$, and let
$T_{M}\subset T_{L}$ be the set of main timelines. A _trunk-and-branch
timeline_ for $G_{TM}$ is a tuple $TBT(G_{TM})=\langle G_{TBT},T_{M}\rangle$,
where $G_{TBT}$ is the graph obtained from concatenating121212The
_concatenation_ of two normal form timelines $L_{1}$ and $L_{2}$, of graph
$G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ respectively, is defined in a
natural way as follows. Suppose, without loss of generality, that timeline
$L_{1}$ precedes timeline $L_{2}$, and the length of $L_{1}$ is $\ell$. Then
the concatenated timeline between $L_{1}$ and $L_{2}$, denoted $L=L_{1}\circ
L_{2}$ with $L:V_{1}(G_{1})\cup V_{2}(G_{2})\to\mathbb{N}$, is defined to be
$L(v)=L_{1}(v)$ if $v\in V_{1}(G_{1})$ and $L(v)=\ell+L_{2}(v)$ if $v\in
V_{2}(G_{2})$. More generally, if $L_{1},L_{2},\ldots,L_{k}$ is a sequence of
normal form timelines arranged in temporally-increasing order, then their
concatenation is defined to be $L=L_{1}\circ L_{2}\circ\cdots\circ L_{k}$.
all timelines in $T_{L}$ together and combined with the set of subordinating
TimeML links between timelines; namely,
$V(G_{TBT})=V_{TM}=\cup_{i=1}^{k}V(G^{(i)}_{TM})$,
$E(G_{TBT})=\left(\bigcup_{i=1}^{k}E(L_{i})\right)\bigcup E_{S}$, and $E_{S}$
is the set of subordinating links between timelines.

######  Definition 4 (Minimum Normal Form Trunk-and-Branch Timeline).

Let $TBT(G_{TM})=\langle G_{TBT},T_{M}\rangle$ be a trunk-and-branch timeline
for a consistent TimeML graph $G_{TM}$ with temporally connected subgraphs
$\\{G^{(1)}_{TM},\ldots,G^{(k)}_{TM}\\}$ and corresponding timelines
$T_{L}=\\{L_{1},\ldots,L_{k}\\}$. We say $TBT(G_{TM})$ is a _normal form
trunk-and-branch timeline_ if every timeline in $T_{L}$ is a normal form
timeline. Furthermore, we say $TBT(G_{TM})$ is the _minimum normal form trunk-
and-branch timeline_ if every timeline in $T_{L}$ is a minimum normal form
timeline.

By combining the algorithms and running time analysis in Sections 3.2, 3.3,
3.4, 3.5 and 3.6, we finally arrive at the following end-to-end main theorem
of tlex:

######  Theorem 1.

On an input of TimeML graph $G_{TM}=(V_{TM},E_{TM})$, with temporally
connected subgraphs $\\{G^{(1)}_{TM},\ldots,G^{(k)}_{TM}\\}$. Let
$V_{M}\subset V_{TM}$ be a subset of events or times which are identified as
on “main timelines”. Then tlex produces one of the two following outputs:

  * •

if all $\\{G^{(i)}_{TM}\\}_{i\in[k]}$ are consistent, tlex outputs

    1. 1.

the minimum normal-form trunk-and-branch timeline $TBT(G_{TM})=\langle
G_{TBT},T_{M}\rangle$ for $G_{TM}$, and every $i\in[k]$ such that
$V(L_{i})\cap V_{M}\neq\emptyset$ is identified as a main timeline; and

    2. 2.

a list of indeterminacy tables $\\{ID_{1},\ldots,ID_{k}\\}$ such that table
$ID_{i}$ stores whether there is indeterminacy between each pair of time-
points in timeline $L_{i}$.

  * •

If some $G^{(i)}_{TM}$ is inconsistent, tlex outputs a Maximal List of
Inconsistent Cycles (MLIC) for each inconsistent temporally connected
subgraph.

Moreover, the running time of tlex is at most $O(n^{2}m+n^{3})$, where $n$ is
the number of events or time expressions and $m$ is the number of TimeML links
in the input TimeML graph.

##  4 Experimental Evaluation

We now discuss our experimental evaluations and show that tlex performs as
expected on real data. We evaluated tlex on the four corpora described
previously in Table 2. As described in §3.4, we ran Consistency Checking
across all inconsistent texts and manually corrected those TimeML graphs with
reference to the original text. To emphasize the importance of alinks, we
performed inconsistency detection on TimeML graphs with and without alinks.
Table 3 shows the number of inconsistent files in corpora. Without alinks,
tlex determined that 30 texts across the four corpora had inconsistent TimeML
graphs. Importantly, these inconsistencies are exactly the same 30 as those
found by Derczynski and Gaizauskas (2010), which checks the consistency of the
TimeML graphs by transforming them into PA graphs and applying their closure
algorithm. But more importantly, the number of inconsistent texts increases
significantly when alinks are included. To correct these inconsistencies, we
removed self-loops automatically and manually corrected larger cycles. All
manual corrections were by reference to the original texts. We produced fully
consistent TimeML graphs for all 385 texts. In some cases, we corrected
inconsistencies by removing an incorrect link in the original TimeML graph; in
other cases by changing an incorrectly labeled link. The details of the
corrections to TimeBank are reported elsewhere (Ocal et al., 2022a).

Corpus | Total Files | Inconsistent Files | Inconsistent Files
---|---|---|---
|  |  (tlinks only) |  (tlinks & alinks)
Timebank | 183 | 30 | 65
N2 Corpus | 67 | 10 | 11
ProppLearner | 15 | 9 | 11
MEANTIME | 120 | 36 | 36*
Total | 385 | 85 | 123
Table 3: Details of the inconsistencies of the four corpora. *The MEANTIME
corpus does not have alinks.

After correction, we extracted the minimum normal form timeline for each text
using the tlex Timeline Generation step and identified their indeterminate
sections using tlex Indeterminacy Detection. Table 4 shows statistics on the
length of the minimum main timelines (i.e., the number of time steps in the
minimum solution), the number of subordinated timelines, and the number of
indeterminate sections.

Our experiments took less than a minute for the entire 385 TimeML annotated
files from four corpora on a current, standard consumer laptop (2.4 GHz 4-core
Intel i7 3630QM with 8GB of RAM).

| Length of | # Subordinated | # of Indeterminate
---|---|---|---
| Main Timeline | Branches / Text | Sections / Text
Corpus | Min | Avg | Max | Min | Avg | Max | Min | Avg | Max
TimeBank | 4 | 8.1 | 18 | 1 | 16.0 | 142 | 0 | 5.3 | 11
N2 Corpus | 6 | 24.7 | 72 | 1 | 19.3 | 106 | 0 | 10.2 | 21
ProppLearner | 128 | 180.5 | 290 | 33 | 82.7 | 134 | 0 | 28.8 | 63
MEANTIME | 4 | 7.3 | 13 | 0 | 2.0 | 7 | 0 | 3.8 | 7
Total | 4 | 17.5 | 290 | 0 | 14.8 | 142 | 0 | 6.6 | 63
Table 4: Details of the timelines extracted from the four corpora.

###  4.1 Sampling Evaluation

As we do not have gold-standard annotated timelines against which to compare,
we cannot directly compute recall, precision, or $F_{1}$ for the output of
tlex. Therefore we performed a sampling evaluation to check the extracted
timelines, where we selected aspects of timelines at random to check against
the original texts. We used Simple Random Sampling (SRS) (Saunders et al.,
2009, p. 222) wherein every member of a population has an equally likely
chance of being selected. In SRS, we check the correctness of a specific
feature of a set of $n$ members randomly selected from a population with size
$N$ to obtain an estimate of the correctness of that feature over all the
data. The formula for calculating sample size for a finite population is:

$n=\frac{n_{0}}{1+\frac{n_{0}-1}{N}}\quad\mathrm{where}\quad
n_{0}=\frac{Z^{2}}{4c^{2}}$

Where $c$ is the confidence interval, $Z$ is the $Z$-score for the confidence
level, and $N$ is the population size. For all experiments, we used a $c$ of
$0.02(2\%)$ and a confidence level of $0.95(95\%)$, which corresponds to a
$Z$-score of $1.96$.

Evaluation experiments were performed by the first author and an independent
annotator that we hired. Both the annotator and the first author performed SRS
separately, and we calculated the inter-annotator agreement (IAA) score based
on their results. We evaluated our extracted timelines via simple random
sampling, checking five features: (1) the ordering of time-points with respect
to each other, (2) the number of main timelines, (3) the placement of events
on main versus subordinated timelines, (4) the connecting point of
subordinated timelines, and (5) whether indeterminate sections are truly
indeterminate with respect to the underlying TimeML graph.

###  4.2 Time-point Ordering

Time-point ordering was the first feature we evaluated. We randomly picked
neighboring pairs of time-points from the tlex-generated timelines and
compared them to the TimeML graph to ensure that the timeline and the graph
were consistent. For example, if we examined a pair of neighboring points
labeled A+ and B-, we examined the paths in the TimeML graph between A and B
to determine if this ordering was correct. Using SRS, we selected 2,264 pairs
of time-points out of 39,534 possible neighboring assignment pairs, sampled
from each corpus in proportion to the total number of time-points in each.
Both the independent annotator and the first author evaluated the correctness
of the ordering, and found each pair to be correctly ordered with respect to
the original text (IAA kappa score $\kappa=1$). Since the confidence interval
is $2\%$, this results in an estimated accuracy of $$98100$\%$ with $95\%$
confidence. Unlike prior approaches, tlex achieves a perfect ordering
accuracy, modulo sampling error and correctness of the TimeML graph, using all
relation types.

###  4.3 Number of Main Timelines

Identification of the main timelines requires identification of at least one
event or time on each main timeline, which is a laborious process. We
approximated this identification, therefore, by identifying as main timelines
all timelines that did not have incoming subordination links from another
timeline in the trunk-and-branch timeline.

With this identification in hand, we assessed whether multiple main timelines
actually corresponded to temporally disjoint and otherwise unrelatable graphs.
In texts with multiple main timelines, we define the breaking pair between two
timelines as the pair of events, times, or an event and time, one from each
timeline, which are closest in the text measured by number of intervening
words. Because the population size (1,241) was not substantially larger than
the sample size (818), we manually checked all breaking pairs in our extracted
timelines, and whether they actually indicated disjoint timelines. Both the
annotator and the first author observed that all of the breaking pairs
corresponded with true disjoint breaks between timelines in the texts (IAA
kappa score $\kappa=1$).

For some cases, we observed that sometimes a text had multiple timelines which
were disjoint, but should have been collected together into a single main
timeline because they were temporally relatable. This is because the
annotation of the text is missing a relation between one group of events or
times and another group of events or times, but in both cases those events
occur in the “real world” of the text. In other words, the TimeML graph was
disconnected in a way that was inconsistent with the actual semantics of the
text, meaning the TimeML annotation was incorrect. We observed this situation
for 181 texts, which is another dimension along which the TimeML annotations
for these corpora might be improved. In our other work, we investigated the
disconnectivity in TimeML graphs and showed that these disconnectivities
mainly occur by a missing link between two subgraphs due to a manual
annotation error (Ocal et al., 2022b). We corrected these erroneous
disconnections in other work (Ocal et al., 2022a).

###  4.4 Time-point Placement

We evaluated whether time-points were correctly placed on main versus
subordinated timelines, using our approximation for main timelines as
indicated previously. The first author and the annotator checked to see if a
time-point placed on a subordinate timeline did not occur in the “real world”
described in the text. 11,474 time-points were on subordinated timelines, and
we sampled 1,986 time-points across the corpora, again in proportion to their
number in each corpus. Again, all samples were correct (IAA kappa score
$\kappa=1$), giving an estimated accuracy of $$98100$\%$ with $95\%$
confidence.

###  4.5 Subordinated Connecting Points

We checked to confirm that subordinated timelines were connected to the
correct time-points on the identified main timelines. There are 5,701
subordinated timelines in our data, and every one was connected to a main
timeline with at least one subordinating link. The first author and the
annotator checked 1,690 connections, observing that every connection was
correctly placed (IAA kappa score $\kappa=1$), giving an estimated accuracy of
$$98100$\%$ with $95\%$ confidence.

###  4.6 Indeterminate Sections

Finally, the first author and the annotator checked whether indeterminate
sections were truly indeterminate with respect to the TimeML graph. There are
2,541 indeterminate sections, comprising 11,688 pairs of time-points. We
randomly selected 1,992 time-point pairs from the indeterminate sections. In
all cases the pairs were truly indeterminate (IAA kappa score $\kappa=1$),
meaning an estimated accuracy of $$98100$\%$ with a $95\%$ confidence.

##  5 Future Work

Our work naturally suggests several interesting directions of future research.

Our investigation showed that manually annotated TimeML texts often contain
errors that result in temporal inconsistencies; automatic methods for
generating TimeML annotations are currently even more noisy and error-prone.
Because of this, a logical next step is to develop methods that automatically
suggest corrections to the maximal list of inconsistent cycles identified in
the Consistency Checking step. Both rule-based and supervised machine
learning-based approaches could be developed to address this problem.

Finally, it is interesting to investigate the performance of tlex on
automatically generated TimeML graphs. Indeed, tlex may be applied in this way
to measure the quality of the timelines extracted, which provides a good
indication of how useful automatic TimeML extraction is in practice.

##  6 Contributions

In this work, we developed tlex (TimeLine EXtraction), an exact, end-to-end
solution which extracts timelines from TimeML annotated texts. The novel
features of tlex include identifying specific relations that are involved in
an inconsistency (which can then be manually corrected) and determining
sections of the timelines that have indeterminate order, which is critical for
downstream tasks such as aligning events from different timelines. We provide
efficient algorithms which implement the tasks within tlex and conduct
experimental evaluations by applying tlex to 385 TimeML annotated texts from
four corpora. We provide a reference implementation of tlex, the extracted
timelines for all texts, and the manual corrections to the temporal graphs of
the inconsistent texts.

##  7 Acknowledgments

We gratefully acknowledge valuable discussions with Jared Hummer, Antonela
Radas, Victor Yarlott, Karine Megerdoomian, Akul Singh, and Emmanuel Garcia.
Contributions to the implementation of the TLEX algorithm in Java and python
were made by FIU KFSCIS Senior Project team members Christopher Eberhard,
Stephan Belizaire, Pablo Maldonado, Luis Robaina, Adrian Silva, Victoria
Fernandez, Ronald Pena, Ismael Clark, Felipe Arce, Kevin Fontela, Raul Garcia,
Leandro Estevez, Carlos Pimentel, Hector Borges, Ivan Parra Sanz, Tony Erazo,
Sage Pages, Gerardo Parra, and Franklin Bello Romero. This work was partially
funded by research grants TO-134841, TO-135998, and TO-139837 to Dr. Finlayson
from MITRE Corporation. Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the author(s) and do
not necessarily reflect the views of MITRE Corporation. This work was also
partially supported by ONR Award N00014-17-1-2983 to Dr. Finlayson.

## References

  * Saquete et al. [2004] E. Saquete, P. Martínez-Barco, R. Muñoz, and J. L. Vicedo.  Splitting complex temporal questions for question answering systems.  In _Proceedings of the 42Nd Annual Meeting on Association for Computational Linguistics_ , ACL ’04, Stroudsburg, PA, USA, 2004. Association for Computational Linguistics.  doi:10.3115/1218955.1219027.  URL https://doi.org/10.3115/1218955.1219027.
  * Navarro-Colorado and Saquete [2016] Borja Navarro-Colorado and Estela Saquete.  Cross-document event ordering through temporal, lexical and distributional knowledge.  _Know.-Based Syst._ , 110(C):244–254, October 2016.  ISSN 0950-7051.  doi:10.1016/j.knosys.2016.07.032.  URL https://doi.org/10.1016/j.knosys.2016.07.032.
  * Liu et al. [2012] Shixia Liu, Michelle X. Zhou, Shimei Pan, Yangqiu Song, Weihong Qian, Weijia Cai, and Xiaoxiao Lian.  Tiara: Interactive, topic-based visual text summarization and analysis.  _ACM Trans. Intell. Syst. Technol._ , 3(2):25:1–25:28, February 2012.  ISSN 2157-6904.  doi:10.1145/2089094.2089101.  URL http://doi.acm.org/10.1145/2089094.2089101.
  * Verhagen et al. [2005] Marc Verhagen, Inderjeet Mani, Roser Sauri, Robert Knippen, Seok Bae Jang, Jessica Littman, Anna Rumshisky, John Phillips, and James Pustejovsky.  Automating temporal annotation with tarsqi.  In _Proceedings of the ACL 2005 on Interactive Poster and Demonstration Sessions_ , pages 81–84, 2005.  Ann Arbor, Michigan.
  * Pustejovsky et al. [2003a] James Pustejovsky, Patrick Hanks, Roser Saurí, Andrew See, Rob Gaizauskas, Andrea Setzer, Dragomir Radev, Beth Sundheim, David Day, Lisa Ferro, and Marcia Lazo.  The TimeBank corpus.  In _Proceedings of Corpus Linguistics Conference_ , pages 647–656, 2003a.  Lancaster, UK.
  * Allen [1983] James F. Allen.  Maintaining knowledge about temporal intervals.  _Communications of the ACM_ , 26(11):832–843, November 1983.  ISSN 0001-0782.  doi:10.1145/182.358434.  URL http://doi.acm.org/10.1145/182.358434.
  * Sauri et al. [2006] Roser Sauri, Jessica Littman, Robert Gaizauskas, Andrea Setzer, and James Pustejovsky.  TimeML annotation guidelines, version 1.2.1, 2006.  https://catalog.ldc.upenn.edu/docs/LDC2006T08/timeml_annguide_1.2.1.pdf.
  * Barták et al. [2014] R. Barták, R.A. Morris, and K.B. Venable.  _An Introduction to Constraint-Based Temporal Reasoning_.  Morgan & Claypool Publishers, 2014.
  * Kreutzmann and Wolter [2014] Arne Kreutzmann and Diedrich Wolter.  Qualitative spatial and temporal reasoning with and/or linear programming.  In _Proceedings of the Twenty-first European Conference on Artificial Intelligence_ , ECAI’14, pages 495–500, Amsterdam, The Netherlands, The Netherlands, 2014. IOS Press.  ISBN 978-1-61499-418-3.  doi:10.3233/978-1-61499-419-0-495.  URL https://doi.org/10.3233/978-1-61499-419-0-495.
  * van Beek [1992] Peter van Beek.  Reasoning about qualitative temporal information.  _Artificial Intelligence_ , 58(1-3):297–326, 1992.
  * Gereveni and Schubert [1995] Alfonso Gereveni and Lenhart Schubert.  Efficient algorithms for qualitative reasoning about time.  _Artif. Intell._ , 74(2):207–248, April 1995.  ISSN 0004-3702.  doi:10.1016/0004-3702(94)00016-T.  URL https://doi.org/10.1016/0004-3702(94)00016-T.
  * Ning et al. [2018] Qiang Ning, Hao Wu, and Dan Roth.  A multi-axis annotation scheme for event temporal relations.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1318–1328, Melbourne, Australia, July 2018. Association for Computational Linguistics.  doi:10.18653/v1/P18-1122.  URL https://aclanthology.org/P18-1122.
  * Ligozat [2013] Gérard Ligozat.  _Qualitative spatial and temporal reasoning_.  John Wiley & Sons, 2013.
  * Vilain and Kautz [1986] Marc B Vilain and Henry A Kautz.  Constraint propagation algorithms for temporal reasoning.  In _AAAI_ , volume 86, pages 377–382, 1986.
  * Vilain et al. [1990] Marc Vilain, Henry Kautz, and Peter van Beek.  Constraint propagation algorithms for temporal reasoning: A revised report.  In Daniel S. Weld and Johan de Kleer, editors, _Readings in Qualitative Reasoning About Physical Systems_ , pages 373–381. Morgan Kaufmann, San Francisco, CA, 1990.
  * Freksa [1992] Christian Freksa.  Temporal reasoning based on semi-intervals.  _Artificial intelligence_ , 54(1-2):199–227, 1992.
  * Nebel and Bürckert [1995] Bernhard Nebel and Hans-Jürgen Bürckert.  Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra.  _J. ACM_ , 42(1):43–66, January 1995.  ISSN 0004-5411.  doi:10.1145/200836.200848.  URL https://doi.org/10.1145/200836.200848.
  * Leeuwenberg and Moens [2019] Artuur Leeuwenberg and Marie-Francine Moens.  A survey on temporal reasoning for temporal information extraction from text.  _Journal of Artificial Intelligence Research_ , 66:341–380, 2019.
  * Dechter et al. [1991] Rina Dechter, Itay Meiri, and Judea Pearl.  Temporal constraint networks.  _Artificial intelligence_ , 49(1-3):61–95, 1991.
  * Ostuni et al. [2021] Dario Ostuni, Alice Raffaele, Romeo Rizzi, and Matteo Zavatteri.  Faster and better simple temporal problems.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 11913–11920, 2021.
  * Setzer [2001] Andrea Setzer.  _Temporal Information in Newswire Articles: an Annotation Scheme and Corpus Study_.  PhD thesis, University of Sheffield, 2001.
  * Ferro et al. [2001] L. Ferro, L. Gerber, I. Mani, B. Sundheim, and G. Wilson.  Tides temporal annotation guidelines, ver. 1.0.2, 2001.  http://www.timeml.org/terqas/readings/MTRAnnotationGuide_v1_02.pdf.
  * Pustejovsky et al. [2003b] James Pustejovsky, José Castaño, Robert Ingria, Roser Saurí, Robert Gaizauskas, Andrea Setzer, and Graham Katz.  TimeML: robust specification of event and temporal expressions in text.  In _Fifth International Workshop on Computational Semantics (IWCS-5)_ , pages 1–11, 2003b.  URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.161.8972&rep=rep1&type=pdf.
  * Llorens et al. [2015] Hector Llorens, Nathanael Chambers, Naushad UzZaman, Nasrin Mostafazadeh, James Allen, and James Pustejovsky.  Semeval-2015 task 5: Qa tempeval-evaluating temporal information understanding with question answering.  In _proceedings of the 9th International Workshop on Semantic Evaluation (SemEval 2015)_ , pages 792–800, 2015.
  * Valdes-Perez [1986] Raul E Valdes-Perez.  Spatio-temporal reasoning and linear inequalities.  Technical report, MIT Artificial Intelligence Laboratory, 1986.
  * Valdes-Perez [1987] Raul E Valdes-Perez.  The satisfiability of temporal constraint networks.  In _Proceedings of the Sixth National Conference on Artificial Intelligence_ , pages 256–260, 1987.
  * Finlayson [2017] Mark A. Finlayson.  Propplearner: Deeply annotating a corpus of russian folktales to enable the machine learning of a russian formalist theory.  _Digital Scholarship in the Humanities_ , 32(2):284–300, 2017.  doi:10.1093/llc/fqv067.  URL +http://dx.doi.org/10.1093/llc/fqv067.
  * Finlayson et al. [2014] Mark Finlayson, Jeffry Halverson, and Steven Corman.  The N2 corpus: a semantically annotated collection of islamist extremist stories.  In _Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14)_ , 2014.  Reykjavik, Iceland.
  * Minard et al. [2016] Anne-Lyse Minard, Manuela Speranza, Ruben Urizar, Begoña Altuna, Marieke van Erp, Anneleen Schoen, and Chantal van Son.  MEANTIME, the newsreader multilingual event and time corpus.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016)_ , 2016.  Portorož, Slovenia.
  * Bethard [2013] Steven Bethard.  ClearTK-TimeML: A minimalist approach to TempEval 2013.  In _Second joint conference on lexical and computational semantics (* SEM), volume 2: Proceedings of the Seventh International Workshop on Semantic Evaluation (SemEval 2013)_ , pages 10–14, 2013.
  * Chambers et al. [2014] Nathanael Chambers, Taylor Cassidy, Bill McDowell, and Steven Bethard.  Dense event ordering with a multi-pass architecture.  _Transactions of the Association for Computational Linguistics_ , 2:273–284, 2014.
  * Mirza and Tonelli [2016] Paramita Mirza and Sara Tonelli.  Catena: Causal and temporal relation extraction from natural language texts.  In _Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers_ , pages 64–75, 2016.
  * Zhang and Xue [2018] Yuchen Zhang and Nianwen Xue.  Neural ranking models for temporal dependency structure parsing.  _CoRR_ , abs/1809.00370, 2018.  URL http://arxiv.org/abs/1809.00370.
  * Wallgrün et al. [2006] Jan Oliver Wallgrün, Lutz Frommberger, Diedrich Wolter, Frank Dylla, and Christian Freksa.  Qualitative spatial representation and reasoning in the sparq-toolbox.  In _Proceedings of the International Conference Spatial Cognition_ , pages 39–58, Bremen, Germany, 09 2006.  doi:10.1007/978-3-540-75666-8_3.
  * Gantner et al. [2008] Zeno Gantner, Matthias Westphal, and Stefan Wolfl.  Gqr - a fast reasoner for binary qualitative constraint calculi, 2008.
  * Sioutis and Condotta [2014] Michael Sioutis and Jean-François Condotta.  Tackling large qualitative spatial networks of scale-free-like structure.  In _Proceedings of the 8th Hellenic Conference on AI (SETN 2014)_ , volume 8445, pages 178–191, Ioannina, Greece, 05 2014.  doi:10.1007/978-3-319-07064-3_15.
  * Swan and Allan [2000] Russell Swan and James Allan.  Automatic generation of overview timelines.  In _Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval_ , pages 49–56, 2000.
  * Allan et al. [2001] James Allan, Rahul Gupta, and Vikas Khandelwal.  Temporal summaries of new topics.  In _Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval_ , pages 10–18, 2001.
  * Ghalandari and Ifrim [2020] Demian Gholipour Ghalandari and Georgiana Ifrim.  Examining the state-of-the-art in news timeline summarization.  In _Proceedings of the 58th Annual Meeting on Association for Computational Linguistics_ , pages 1322–1334, 2020.
  * Mani et al. [2006] Inderjeet Mani, Marc Verhagen, Ben Wellner, Chong Min Lee, and James Pustejovsky.  Machine learning of temporal relations.  In _Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics (ICCL-ACL’06)_ , pages 753–760, 2006.  Sydney, Australia.
  * Do et al. [2012] Quang Xuan Do, Wei Lu, and Dan Roth.  Joint inference for event timeline construction.  In _Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL’12)_ , pages 677–687, 2012.
  * Kolomiyets et al. [2012] Oleksandr Kolomiyets, Steven Bethard, and Marie-Francine Moens.  Extracting narrative timelines as temporal dependency structures.  In _Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (ACL’12)_ , pages 88–97, 2012.
  * Ocal and Finlayson [2020] Mustafa Ocal and Mark Finlayson.  Evaluating information loss in temporal dependency trees.  In _Proceedings of The 12th Language Resources and Evaluation Conference_ , pages 2148–2156, Marseille, France, May 2020. European Language Resources Association.  ISBN 979-10-95546-34-4.  URL https://www.aclweb.org/anthology/2020.lrec-1.263.
  * Leeuwenberg and Moens [2020] Artuur Leeuwenberg and Marie-Francine Moens.  Towards extracting absolute event timelines from English clinical reports.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 28:2710–2719, 2020.
  * Mathur et al. [2022] Puneet Mathur, Vlad Morariu, Verena Kaynig-Fittkau, Jiuxiang Gu, Franck Dernoncourt, Quan Tran, Ani Nenkova, Dinesh Manocha, and Rajiv Jain.  DocTime: A document-level temporal dependency graph parser.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 993–1009, Seattle, United States, July 2022. Association for Computational Linguistics.  doi:10.18653/v1/2022.naacl-main.73.  URL https://aclanthology.org/2022.naacl-main.73.
  * Verhagen et al. [2006] Marc Verhagen, Robert Knippen, Inderjeet Mani, and James Pustejovsky.  Annotation of temporal relations with Tango.  In _LREC_ , pages 2249–2252, 2006.
  * Verhagen [2007] Marc Verhagen.  Drawing timeml relations with tbox.  In _Annotating, extracting and reasoning about time and events_ , pages 7–28. Springer, 2007.
  * Cormen et al. [2022] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  _Introduction to Algorithms_.  MIT press, 2022.
  * Iwata and Yoshida [2013] Yoichi Iwata and Yuichi Yoshida.  Exact and Approximation Algorithms for the Maximum Constraint Satisfaction Problem over the Point Algebra.  In Natacha Portier and Thomas Wilke, editors, _30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)_ , volume 20 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 127–138, Dagstuhl, Germany, 2013. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  ISBN 978-3-939897-50-7.  doi:10.4230/LIPIcs.STACS.2013.127.  URL http://drops.dagstuhl.de/opus/volltexte/2013/3928.
  * Condotta et al. [2016] Jean-François Condotta, Issam Nouaouri, and Michael Sioutis.  A SAT approach for maximizing satisfiability in qualitative spatial and temporal constraint networks.  In _Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning_ , KR’16, page 432–442. AAAI Press, 2016.
  * Kahn [1962] Arthur B Kahn.  Topological sorting of large networks.  _Communications of the ACM_ , 5(11):558–562, 1962.
  * Derczynski and Gaizauskas [2010] Leon Derczynski and Robert J. Gaizauskas.  Analysing temporally annotated corpora with CAVaT.  In _Proceedings of the Seventh conference on International Language Resources and Evaluation (LREC’10)_ , 2010.  Valetta, Malta.
  * Ocal et al. [2022a] Mustafa Ocal, Antonela Radas, Jared Hummer, Karine Megerdoomian, and Mark Finlayson.  A comprehensive evaluation and correction of the TimeBank corpus.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 2919–2927, Marseille, France, 2022a.  URL https://aclanthology.org/2022.lrec-1.313.
  * Saunders et al. [2009] M.N.K. Saunders, Philip Lewis, and Adrian Thornhill.  _Research Methods for Business Students, Fifth Edition_.  Prentice Hall, New York, 2009.
  * Ocal et al. [2022b] Mustafa Ocal, Adrian Perez, Antonela Radas, and Mark Finlayson.  Holistic evaluation of automatic timeml annotators.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 1444–1453, 2022b.