# Namesakes:
Ambiguously Named Entities from Wikipedia and News

Oleg Vasilyev, Aysu Altun, Nidhi Vyas, Vedant Dharnidharka, Erika Lam, John
Bohannon
Primer Technologies Inc.
San Francisco, California
<EMAIL_ADDRESS>
* Currently at Galileo Technologies

###### Abstract

We present Namesakes, a dataset of ambiguously named entities obtained from
English-language Wikipedia and news articles. It consists of 58862 mentions of
4148 unique entities and their namesakes: 1000 mentions from news, 28843 from
Wikipedia articles about the entity, and 29019 Wikipedia backlink mentions.
Namesakes should be helpful in establishing challenging benchmarks for the
task of named entity linking (NEL).

##  1 Introduction

Recent advances have made it possible to incorporate knowledge into
distributed neural representations Min et al. (2020); Nooralahzadeh and
Øvrelid (2018). A fundamental component of such systems is named entity
linking (NEL) Yang and Chang (2015); Sorokin and Gurevych (2018); Kolitsas et
al. (2018); Li et al. (2020); Sevgili et al. (2021). Given a text, the task is
to correctly identify mentions of named entities by linking to the correct
reference entities in a knowledge base, e.g. Wikipedia. As the world evolves,
new entities and new information about existing entities must be tracked with
a dynamic knowledge base.

If every entity had a unique name like a bar code, NEL would be easy. But we
live in a world populated by "Michael Jordan", a name shared by a renowned
computer scientist, a famous basketball player, a famous actor, and many
others. There are more than 20 entities with the surface form "Michael
Jackson" in
Wikipedia111en.wikipedia.org/wiki/Michael_Jackson_(disambiguation), and the
Wikipedia Disambiguation pages for some names include hundreds of unique
entities.222en.wikipedia.org/wiki/Aliabad

In some definitions of NEL the task includes named entity recognition (NER),
the initial tagging of named entity mentions in the target text Yang and Chang
(2015); Sorokin and Gurevych (2018); Kolitsas et al. (2018); Li et al. (2020);
Sevgili et al. (2021). Here we focus on the more narrow sense of NEL which
assumes the initial tagging of named entities is done Rao et al. (2012); Wu et
al. (2020); Logeswaran et al. (2019). The mentions of entities in a text
corpus are generally provided as spans that capture various surface forms. For
example for the entity Michael Jordan, some mentions include M. Jordan,
Jordan, Michael Jordan.

Most existing NEL-related datasets do not focus on highly ambiguous names,
e.g. WikiDisamb30 Ferragina and Scaiella (2012), ACE and MSNBC Ratinov et al.
(2011), WNED-CWEB and WNED-WIKI Guo and Barbosa (2018) CoNLL-YAGO Hoffart et
al. (2011), and TAC KBP Entity Discovery and Linking dataset Ji et al. (2017).
The recently introduced Ambiguous Entity Retrieval (AmbER) dataset by Chen et
al. (2021) is an exception, including subsets of identically named entities
for the purpose of fact checking, slot filling, and question-answering tasks.
AmBer is limited to Wikipedia text and was automatically generated.

The unique contribution of the Namesakes Vasilyev et al. (2021)
dataset333figshare.com/articles/dataset/Namesakes/17009105/1 is its
diversity—it includes news mentions—and its high quality, ensured by manual
data-labeling. The importance of manual labeling will become clear in the data
description that follows. In this paper we describe in detail the data
selection, filtering, and composition of Namesakes. We also define and present
the ambiguity of the mentions of entities in Namesakes. The aim of Namesakes
is to help researchers distinguish the performance of NEL systems with highly
challenging, realistic data.

##  2 Dataset composition

###  2.1 Data motivation

The primary motivation for this work is to create a more challenging NEL
dataset where:

  1. 1.

The names of most entities must be ambiguous, i.e. with Wikipedia
disambiguation pages linking to multiple Wikipedia articles.

  2. 2.

Most entities must belong to one of three categories - person, location,
organization - preferably in balanced proportions.

  3. 3.

Entity contexts are captured by three distinct components:

    1. (a)

Entities: Wikipedia articles describing named entities

    2. (b)

Backlinks: Wikipedia articles that reference members of Entities

    3. (c)

News: News articles containing mentions from Entities. The News mentions may
be true references to members of Entities or have name collisions with them.

  4. 4.

All three components should have reasonably clean text chunks (at least in the
neighborhood of the entities of interest), filtered for obscure reference
sections, business reports, TV listings, etc.

The initial entities names we selected are listed in the Appendix A. Only
names with a Wikipedia disambiguation page are included, resulting in an
initial count of 7626 Wikipedia entities.

###  2.2 Entities: selection for labeling

We filtered the preliminary 7626 Wikipedia entities by requiring that each
text satisfies several reasonable conditions:

  1. 1.

The text must contain at least 5 "good sentences", after sentence tokenization
with NLTK. The "good sentence" empirical conditions are listed in Appendix B.

  2. 2.

The first named entity identified in the text by an NER model must be a person
PER, organization ORG or location LOC, not miscellaneous MISC. We performed
NER using the "bert-large-cased-finetuned-conll03-english" model from the
Hugging Face model hub444https://huggingface.co/dbmdz/bert-large-cased-
finetuned-conll03-english.

  3. 3.

The text must contain at least 3 mentions that are similar to the Wikipedia
entity’s name. These entities should be picked up only from the "good
sentences". The similarity here means that an entity contains at least one
word from the entity name with length >=3 characters. The motivation for this
is to exclude abnormally short Wikipedia entities, or at least have an entity
containing entities that can be confused with the "main" entity.

With the highly ambiguous entities we started with, and after the above
filtering, the resulting Wikipedia pages had a high frequency of intentionally
confusing entities. Most of the ambiguity derives from having similar or
identical names shared among multiple Wikipedia entities. Additional confusion
comes from a Wikipedia entity text frequently having not only the "main"
entity (the main focus of the article), but additional entities with the same
or similar names described in the article. These additional entities are often
relatives of a "main" person entity, or locations and organizations of the
same or similar name.

The goal of our labeling was to identify in each entity the "main" entity and
the "other" entities. In our final selection for labeling, we selected top
entity names by the number of Wikipedia pages in which such names occurred.
Specifically, the top 100 names of each type were selected: person,
organization, location. Our resulting dataset for labeling contains 4148
Wikipedia entities. For each entity text, all the entities with the names
similar to the name of the entity were tagged as "categorize", requesting
annotators to replace the tag by either "Same" or "Other". The tag "Same"
means that the entity is actually the entity, i.e. the entity to which the
entity text is devoted to. The tag "Other" means that, despite the same or
similar name, the tagged entity is not the entity.

###  2.3 Entities data

The labeled Entities data is the output of our manual labeling process,
undertaken by an annotation team at Odetta555https://odetta.ai using the
annotation software tool Datasaur666https://datasaur.ai. The team consisted of
6 annotators who were experienced with NLP projects and passed a trial
training task for this project. Only the most reliable tagged entity mentions
were kept:

  1. 1.

The mentions to which all six annotators assigned the "Same" tag.

  2. 2.

The mentions on which only one annotator disagreed with the rest; such
mentions were confirmed via reconciliation.

The final result was 21426 "Same" mentions and 7417 "Other" mentions for the
4148 Wikipedia entities.

###  2.4 News data

The News component of our dataset was created from querying Primer’s
proprietary news corpus by the ambiguous entity names from the Entities
component. The "ambiguous" entities are the entities with the names (aliases,
or last names of people) that could be mixed up with at least three other
entities. Once the news articles were obtained, they were filtered (see
Appendix C) by excluding articles not satisfying the requirements of text
quality and manageable labeling:

  1. 1.

The final number of news texts is 1000.

  2. 2.

Each text is between 500 and 3000 characters.

  3. 3.

Each text has a named entity mention found by the name query; this mention has
to be labeled. The list of suggested labels must contain at least 3 but not
more than 10 Wikipedia entities with which the mention can be confused,
including the entity (if it exists) to which it belongs. Fewer than 3
Wikipedia entities fails to provide enough ambiguity, while more than 10 would
be too time-consuming to label.

The goal of the labeling was to assign to each mention its correct Wikipedia
entity (if existing in the Entities dataset), from the list of 3-10 provided
Wikipedia entities. The labeling was done using the annotation tool Datasaur,
by 3 Odetta annotators, with consequent reconciliation of all the mentions
that caused a disagreement. Similar to the labeling of the Entities, the
annotators were experienced in NLP projects and went through a trial task.

The resulting News data consists of 1000 texts, each text with one annotated
mention. Of these mentions, 276 do exist in the Entities data, and 724 do not
exist in the Entities data (but can be easily confused with many entities from
there).

###  2.5 Backlinks data

The Backlinks dataset was manufactured from a Wikipedia dump from July 1, 2021
by collecting (and then thoroughly filtering for quality) the entities that
link to the Entities dataset. For example, if the person described in the
"John Muir" Wikipedia article were a member of the Entities dataset, then the
"National Park" Wikipedia page would be one of our candidate backlinks,
because its text includes a hyperlink with anchor text "John Muir" that links
to the "John Muir" page.

Many links happen to occur in reference-like sections of Wikipedia rather than
in a normal text; this requires careful filtering. Our filtering and cleaning
included (for details see Appendix D):

  1. 1.

Removing Wikipedia pages with titles that start with certain words, such as
"List", "MediaWiki" etc.

  2. 2.

Removing bottom part of the page text, starting from certain sections, named
like "Notes, "References" etc.

  3. 3.

Only mentions from "good" parts of the Wikipedia page are kept. If a page
loses all its mentions, the page is removed.

  4. 4.

Any page text is cut after 1000 characters down from the last (occurred lowest
in the text) mention.

The resulting Backlinks dataset contains 26903 text chunks from Wikipedia
pages, and 29019 linked mentions in the pages.

###  2.6 Resulting dataset

The resulting dataset Namesakes consists of three closely related datasets:
Entities, News, and Backlinks. The structure of the dataset is shown in Figure
1, the details of the figure will be explained in the following subsections
and in Section 3. The Entities and Backlinks consist of Wikipedia text chunks.
The News consists of random news chunks. The Entities and News are human-
labeled, resolving the mentions of the entities. The Backlinks are not
labeled, but have mentions already linked by Wikipedia. In this section we
summarize the structure of the data.

Figure 1: Structure of Namesakes. An attempt to link a mention to KB (Entities
with "Same" mentions) has a potential confusion - Ambiguity $A$ (discussed in
Section 3 and defined in Appendix E). $N$ is the number of mentions. Some
mentions that refer to KB entities have mentions not existing in the KB, the
percent of such mentions is indicated as "New". Some mentions that should not
belong to KB ("out-KB" News and "Other" Entities) nevertheless have namesakes
of "Same" mentions - as shown by bifurcated arrows. This figure shows only one
possible scenario of possible linking, see Section 4.

####  2.6.1 Entities

The Entities dataset consists of 4148 Wikipedia text chunks containing human-
tagged mentions of entities. Each mention is tagged either as "Same" (meaning
that the mention is of this Wikipedia page entity), or "Other" (meaning that
the mention is of some other entity, just having the same or similar name).
The Entities dataset is a jsonl list, each item is a dictionary with the
following keys and values:

  1. 1.

Key "pagename": page name of the Wikipedia page.

  2. 2.

Key "pageid": page id of the Wikipedia page.

  3. 3.

Key "title": title of the Wikipedia page.

  4. 4.

Key "url": URL of the Wikipedia page.

  5. 5.

Key "entities": list of the mentions in the page text, each entity is
represented by a dictionary with the keys:

    1. (a)

Key "text": the mention as a string from the page text.

    2. (b)

Key "start": start character position of the entity in the text.

    3. (c)

Key "end": end (one-past-last) character position of the entity in the text.

    4. (d)

Key "tag": the annotation tag ("Same" or "Other") given to the mention.

  6. 6.

Key "text": The text chunk.

The texts contain 21426 mentions tagged "Same", and 7417 mentions tagged
"Other".

####  2.6.2 News

The News dataset consists of 1000 news text chunks, each with a single
annotated entity mention. The annotation either points to the corresponding
entity from the Entities dataset (if the mention is of that entity), or
indicates that the mention entity does not belong to the Entities dataset. The
News dataset is a jsonl list, each item is a dictionary with the following
keys and values:

  1. 1.

Key "id_text": Id of the document (0,1,2,3,…).

  2. 2.

Key "entity": a dictionary describing the annotated entity mention in the
text:

    1. (a)

Key "text": the mention as a string found by an NER model in the text.

    2. (b)

Key "start": start character position of the mention in the text.

    3. (c)

Key "end": end (one-past-last) character position of the mention in the text.

    4. (d)

Key "tag": This key exists only if the mentioned entity is annotated as
belonging to the Entities dataset - if so, the value is a dictionary
identifying the Wikipedia page assigned by annotators to the mentioned entity:

      1. i.

Key "pageid": Wikipedia page id.

      2. ii.

Key "pagetitle": page title.

      3. iii.

Key "url": page URL.

  3. 3.

Key "urls": List of URLs of wikipedia entities suggested to labelers for
identification of the entity mentioned in the text.

  4. 4.

Key "text": The text chunk.

Of the 1000 mentions, 276 do exist in the Entities dataset, and the rest do
not (but have the names that could be easily confused with one or more
entities from there).

####  2.6.3 Backlinks

The Backlinks dataset consists of two parts: dictionary Entity-to-Backlinks
and Backlinks documents. The dictionary points to backlinks for each entity of
the Entity dataset (if any backlinks exist for the entity). The Backlinks
documents are the backlinks Wikipedia text chunks with identified mentions of
the entities from the Entities dataset.

Each mention is identified by surrounded double square brackets, e.g. "Muir built a small cabin along [[Yosemite Creek]].". However, if the mention differs from the exact entity name, the double square brackets wrap both the exact name on the left and, separated by ’|’, the mention string on the right, for example: "Muir also spent time with photographer [[Carleton E. Watkins | Carleton Watkins]] and studied his photographs of Yosemite.".

The Entity-to-Backlinks is a jsonl with 1527 items, each item is a tuple:

  1. 1.

Entity name.

  2. 2.

Entity Wikipedia page id.

  3. 3.

Backlinks ids: a list of pageids of backlink documents.

The Backlinks documents is a jsonl with 26903 items, each item is a
dictionary:

  1. 1.

Key "pageid": Id of the Wikipedia page.

  2. 2.

Key "title": Title of the Wikipedia page.

  3. 3.

Key "content": Text chunk from the Wikipedia page, with all mentions in the
double brackets; the text is cut 1000 characters after the last mention, the
cut is denoted as "…[CUT]".

  4. 4.

Key "mentions": List of the mentions from the text, for convenience. Each
mention is a tuple:

    1. (a)

Entity name.

    2. (b)

Entity Wikipedia page id.

    3. (c)

Sorted list of all character indexes at which the mention occurrences start in
the text.

##  3 Dataset features

###  3.1 Entities dataset

The Entities dataset by itself is simple: its 4148 Wikipedia text chunks
contain 28843 annotated mentions, of which 21426 are "Same" and 7417 are
"Other". The 21426 "Same" mentions are occurrences of 2909 unique mentions as
strings. The 7417 "Other" mentions are occurrences of 3754 unique mentions as
strings. The distribution of the entities by the number of the mentions they
have is shown in Figures 2 and 3.

Figure 2: In Entities: Distribution of entities by the number of the mentions
in them. Area of (X,Y) marker is proportional to the number of entities having
X "Same" and Y "Other" mentions. Figure 3: In Entities: Histogram of entities
by the number of the mentions in entity. Two entities (having 23 mentions and
27 mentions) are cut from the histogram. Average number of "Same" mentions per
entity is 5.2.

The 4148 entities of Entities dataset have high overlap of their names. For
example, if we define an "overlap" as two names having at least one common
word of at least 4 characters, then there are 4132 overlapping entities out of
4148. The most overlapping entity is "John William Smith (legal writer)", -
overlaps with 1241 other entities. In our definition of the overlap we
excluded all the bracketed categorizations, like "(legal writer)", because
such words are generic and not really parts of the name. We can characterize
the confusing potential of a dataset by a names overlap, which we define as
the number of entities with which an average entity overlaps by at least one
non-generic word of length >= 4 characters. For Entities dataset we have names
overlap = 379.5.

The real problem for NEL happens when the same mention was used legitimately
for more than one entity. We can characterize potential confusion of NEL
directly in terms of the mentions. How many entities an average mention may
refer to? More specifically, what is the average number of Wikipedia entities
that had at least one "Same" mention coinciding with the considered mention?
This characteristic, mention-entities ambiguity, equals 181.3 for the mentions
"Same", and it equals 20.9 for the mentions "Other" (see Appendix E.1). This
makes a strong potential for confusing NEL. The distribution of individual
ambiguities is shown in Figure 4.

Figure 4: In Entities: cumulative distribution of mentions by the number of
entities using the mention as "Same" (see Appendix E.1). On the right the
total number of mentions reaches 21426 for "Same, and 7417 for "Other". The
average ambiguities is 181.3 for "Same" and 20.9 for "Other".

###  3.2 News - Entities

The News dataset contains 1000 text chunks, each with one mention annotated
either as belonging to the Entities dataset (276 cases), or not (724 cases).
We will call these mentions "to-KB" and "out-KB" mentions correspondingly. The
276 mentions recognized as belonging to the Entities are actually occurrences
of 24 unique mentions. The 724 mentions recognized as not belonging to the
Entities are occurrences of 54 unique mentions.

A strong possibility of confusion for NEL comes from the fact that some unique
mentions from News completely coincide with the "Same" mentions from more than
one entity from the Entities. Even stronger confusion comes from the News
mentions that do not belong to the Entities, but nevertheless exactly coincide
with the "Same" mentions from the Entities. Of 54 unique mentions recognized
as not belonging to Entities, 37 coincide with at least one "Same" mention
from the Entities. This makes 44% of the "Other" mentions occurrences; the
remaining 56%, while having some names overlap, do not exactly coincide with
any "Same" mentions or with exact entity names, - as depicted in Figure 1.

The mention-entities ambiguity is 1.9 for the 276 "to-KB" News mentions, and
it is 1.6 for the 724 "out-KB" News mentions (see Appendix E.2). The
distribution of individual ambiguities is shown in Figure 5.

Figure 5: News to Entities: cumulative distribution of mentions by the number
of entities using the mention as "Same" (see Appendix E.2). On the right the
total number of mentions reaches 276 for "to-KB", and 724 for "out-KB". The
corresponding average ambiguities are 1.9 and 1.6.

###  3.3 Backlinks - Entities

The relation Backlinks-Entities is simpler than the relation News-Entities,
because all the mentions in Backlinks do belong to the Entities (and there was
no need to annotate). All 29019 mention occurrences in Backlinks refer to 1527
entities of the Entities dataset. Since the mention "surface forms" do not
always coincide with the entity names, there are 2399 (rather than 1527)
unique mentions in the Backlinks dataset. We depicted in Figure 1 that 10% of
the mention occurrences do not coincide with any "Same" mentions or entity
names of Entities.

The mention-entities ambiguity equals 7.6 for Backlinks mentions (the
ambiguity is with respect to the Entities, see Appendix E.2). The distribution
of individual ambiguities is shown in Figure 6.

Figure 6: Backlinks to Entities: cumulative distribution of Backlinks mentions
by the number of entities using the mention as "Same" in Entities. On the
right of the plot the total number of mentions reaches 28991 (the remaining 28
mentions are cut from the plot, their number of entities is in the range 100 -
600). The average mention-entities ambiguity is 7.6.

##  4 Discussion

The Namesakes dataset is helpful to us for evaluating NEL models, and we hope
it will be useful as well for the community. High ambiguity makes it easier to
distinguish between otherwise similar performance. There are several scenarios
for using Namesakes for NEL evaluation, depending on the role played by a
knowledge base (KB), and what role is played by external mentions (EM) that
must be linked to the KB.

NEL for an EM mention may either link to a KB entity, or not link to the KB at
all. The first outcome is incorrect in two cases: the mention refers to an
entity which is not in KB, or the linking was done to an incorrect KB entity.
The second outcome is incorrect if the mention refers to an entity existing in
the KB (we will call such a mention a to-KB mention, and we will call any
other mention an out-KB mention).

Problems for an NEL model may come not only from the ambiguity of the EM
mentions with respect to the KB, but also from the difference in style of the
EM texts versus KB texts. In Namesakes, Entities texts are written in clear
Wikipedia style; News texts are more varied and may have much less context
relevant to the mention; and Backlinks texts are in between: still in the
Wikipedia style, but with context not centered around the mention.

A few simple scenarios of splitting Namesakes on EM and KB:

  1. 1.

News to Entities

  2. 2.

Backlinks to Entities

  3. 3.

News to Entities+Backlinks

  4. 4.

Entities to Entities.

  5. 5.

All to All

The News-to-Entities scenario is relevant for evaluating NEL for a situation
where the KB was created from knowledge-friendly texts (in our case Entities
is from Wikipedia), and EM come from accidental encounters with named entities
in varied sources (in our case News texts). As in most scenarios, the
evaluation must include three numbers:

  1. 1.

For to-KB mentions:

    1. (a)

Percent of mentions linked to a wrong KB entity

    2. (b)

Percent of mentions not linked to KB

  2. 2.

For out-KB mentions: percent of mentions linked to KB

Arguably, it is most important to have the third listed percent low, almost as
important to have the first one low, and less important but desirable to have
the second percent low.

The Backlinks-to-Entities scenario still provides some difference between the
EM texts style and the KB texts style, because a backlink text mentions the
entity of interest only incidentally. The Backlinks dataset has only to-KB
mentions, so for simulating out-KB mentions it is necessary to exclude some
entities from the Entities.

The News-to-Entities+Backlinks scenario assumes that the KB is created both
from the Entities and the Backlinks, and thus should be better for linking
from varied texts like News. An NEL system would be expected to perform in
this scenario better than in the News-to-Entities.

The Entities-to-Entities addresses a situation where EM texts are similar to
the KB texts, and provides very high ambiguity of the entities. However, it is
necessary to carefully split the Entities into the mentions and entities for
EM and the mentions and entities for KB.

The All-to-All scenario assumes ’All = Entities + Backlinks + News’, i.e. the
whole Namesakes dataset must be split on EM and KB. This allows insights on
how different kinds of mentions can be useful for creating KB entities, and
how easy it is to link different kinds of EM mentions.

##  5 Conclusion

Advances in named entity linking (NEL) require a sensitive test of performance
to distinguish good from great performance. To that end, we created Namesakes
Vasilyev et al. (2021), a
dataset777figshare.com/articles/dataset/Namesakes/17009105/1 of entities with
highly ambiguous names. In this paper we outline our motivation and method for
data selection, filtering, and composition. We also describe in detail and
define the metrics of ambiguity for these entities.

## Acknowledgments

We thank Spencer Braun for review of the paper and valuable feedback; we thank
Odetta888https://odetta.ai annotators and reconciliators, especially Nusaiba
Khubaib, for high dedication to managing the labeling and verifying the data.

## References

  * Chen et al. (2021) Anthony Chen, Pallavi Gudipati, Shayne Longpre, Xiao Ling, and Sameer Singh. 2021\.  Evaluating entity disambiguation and the role of popularity in retrieval-based nlp.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing_ , pages 4472–4485, Brussels, Belgium. Association for Computational Linguistics.
  * Ferragina and Scaiella (2012) Paolo Ferragina and Ugo Scaiella. 2012.  Fast and accurate annotation of short texts with wikipedia pages.  _IEEE Software_ , 29:70–75.
  * Guo and Barbosa (2018) Zhaochen Guo and Denilson Barbosa. 2018.  Robust named entity disambiguation with random walks.  _Semantic Web_ , 9:459–479.
  * Hoffart et al. (2011) Johannes Hoffart, Mohamed Amir Yosef, Ilaria Bordino, Hagen Fürstenau, Manfred Pinkal, Marc Spaniol, Bilyana Taneva, Stefan Thater, and Gerhard Weikum. 2011.  Robust disambiguation of named entities in text.  In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , pages 782–792, Edinburgh, Scotland, UK. Association for Computational Linguistics.
  * Ji et al. (2017) Heng Ji, Xiaoman Pan, Boliang Zhang, Joel Nothman, James Mayfield, Paul McNamee, and Cash Costello. 2017.  Overview of tac-kbp2017 13 languages entity discovery and linking. In _Text Analysis Conference TAC 2017_.
  * Kolitsas et al. (2018) Nikolaos Kolitsas, Octavian-Eugen Ganea, and Thomas Hofmann. 2018.  End-to-end neural entity linking.  In _Proceedings of the 22nd Conference on Computational Natural Language Learning_ , page 519–529, Brussels, Belgium. Association for Computational Linguistics.
  * Li et al. (2020) Belinda Z. Li, Sewon Min, Srinivasan Iyer, Yashar Mehdad, and Wen-tau Yih. 2020\.  Efficient one-pass end-to-end entity linking for questions.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6433–6441, Online. Association for Computational Linguistics.
  * Logeswaran et al. (2019) Lajanugen Logeswaran, Ming-Wei Chang, Kenton Lee, Kristina Toutanova, Jacob Devlin, and Honglak Lee. 2019.  Zero-shot entity linking by reading entity descriptions.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3449–3460, Florence, Italy. Association for Computational Linguistics.
  * Min et al. (2020) Sewon Min, Danqi Chen, Luke Zettlemoyer, and Hannaneh Hajishirzi. 2020.  Knowledge guided text retrieval and reading for open domain question answering.  _arXiv_ , arXiv:1911.03868v2.
  * Nooralahzadeh and Øvrelid (2018) Farhad Nooralahzadeh and Lilja Øvrelid. 2018.  SIRIUS-LTG: An entity linking approach to fact extraction and verification.  In _Proceedings of the First Workshop on Fact Extraction and VERification (FEVER)_ , pages 119–123, Brussels, Belgium. Association for Computational Linguistics.
  * Rao et al. (2012) Delip Rao, Paul McNamee, and Mark Dredze. 2012.  Entity linking: Finding extracted entities in a knowledge base.  _Multi-source, Multilingual Information Extraction and Summarization_ , pages 93–115.
  * Ratinov et al. (2011) Lev Ratinov, Dan Roth, Doug Downey, and Mike Anderson. 2011.  Local and global algorithms for disambiguation to Wikipedia.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pages 1375–1384, Portland, Oregon, USA. Association for Computational Linguistics.
  * Sevgili et al. (2021) Ozge Sevgili, Artem Shelmanov, Mikhail Arkhipov, Alexander Panchenko, and Chris Biemann. 2021.  Neural entity linking: A survey of models based on deep learning.  _arXiv_ , arXiv:2006.00575v3.
  * Sorokin and Gurevych (2018) Daniil Sorokin and Iryna Gurevych. 2018.  Mixing context granularities for improved entity linking on question answering data across entity categories.  In _Proceedings of the Seventh Joint Conference on Lexical and Computational Semantics_ , pages 65–75, New Orleans, Louisiana. Association for Computational Linguistics.
  * Vasilyev et al. (2021) Oleg Vasilyev, Aysu Altun, Nidhi Vyas, Vedant Dharnidharka, Erika Lampert, and John Bohannon. 2021.  Namesakes.  _figshare. Dataset_ , 10.6084/m9.figshare.17009105.v1.
  * Wu et al. (2020) Ledell Wu, Fabio Petroni, Martin Josifoski, Sebastian Riedel, and Luke Zettlemoyer. 2020.  Scalable zero-shot entity linking with dense entity retrieval.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6397–6407, Online. Association for Computational Linguistics.
  * Yang and Chang (2015) Yi Yang and Ming-Wei Chang. 2015.  S-MART: Novel tree-based structured learning algorithms applied to tweet entity linking.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 504–513, Beijing, China. Association for Computational Linguistics.

##  Appendix A Ambiguous Names

Table 1 contains list of common person names that we used. The names were
taken from the top of the most common names lists
999https://www.ssa.gov/oact/babynames/decades/century.html
101010List_of_most_common_surnames_in_North_America##United_States_(American)

Table 1: Common person names: 10 most common male first names (column 1), female first names (column 2) and last names (column 3). male | female | surname
---|---|---
James | Mary | Smith
Robert | Patricia | Johnson
John | Jennifer | Williams
Michael | Linda | Brown
William | Elizabeth | Jones
David | Barbara | Miller
Richard | Susan | Davis
Joseph | Jessica | Garcia
Thomas | Sarah | Rodriguez
Charles | Karen | Wilson

Combining first and last names from the table gives 200 person names.

List of 35 common location names that we used (from the most common US
locations111111List_of_the_most_common_U.S._place_names): ’Washington’,
’Franklin’, ’Arlington’, ’Centerville’, ’Lebanon’, ’Clinton’, ’Springfield’,
’Georgetown’, ’Fairview’, ’Greenville’, ’Bristol’, ’Chester’, ’Dayton’,
’Dover’, ’Madison’, ’Salem’, ’Oakland’, ’Milton’, ’Newport’, ’Riverside’,
’Ashland’, ’Bloomington’, ’Manchester’, ’Oxford’, ’Winchester’, ’Burlington’,
’Jackson’, ’Milford’, ’Clayton’, ’Mount Vernon’, ’Auburn’, ’Kingston’,
’Lexington’, ’Cleveland’, ’Hudson’.

Initial list of organization names, subject to further check of requirement to
have multiple Wikipedia entities, was combined from several preliminary lists
following below, with entities as they were at May 2021.

Top 40 companies by revenues 121212List_of_largest_companies_by_revenue:
’Walmart’, ’Sinopec Group’, ’Amazon’, ’State Grid’, ’China National
Petroleum’, ’Royal Dutch Shell’, ’Saudi Aramco’, ’Volkswagen’, ’BP’, ’Toyota’,
’Apple’, ’ExxonMobil’, ’CVS Health’, ’Berkshire Hathaway’, ’UnitedHealth’,
’McKesson’, ’Glencore’, ’China State Construction’, ’Samsung Electronics’,
’Daimler’, ’Ping An Insurance’, ’Alphabet’, ’AT&T’, ’AmerisourceBergen’,
’ICBC’, ’Total’, ’Foxconn’, ’Trafigura’, ’Exor’, ’China Construction Bank’,
’Ford’, ’Cigna’, ’Costco’, ’AXA’, ’Agricultural Bank of China’, ’Chevron’,
’Cardinal Health’, ’Microsoft’, ’JPMorgan Chase’, ’Honda’.

Top 14 largest employers 131313List_of_largest_employers: ’U.S. Department of
Defense’, "People’s Liberation Army", ’Walmart’, ’Russian Armed Forces’,
"McDonald’s", ’National Health Service’, ’China National Petroleum
Corporation’, ’State Grid Corporation of China’, ’Indian Railways’, ’Indian
Armed Forces’, "Korean People’s Army", ’Foxconn’, ’French Ministry of National
Education’, ’Amazon’.

Top 10 wealthiest charitable
foundations141414List_of_wealthiest_charitable_foundations: ’Novo Nordisk
Foundation’, ’Bill & Melinda Gates Foundation’, ’Stichting INGKA Foundation’,
’Wellcome Trust’, ’Howard Hughes Medical Institute’, ’Azim Premji Foundation’,
’Garfield Weston Foundation’, ’Lilly Endowment’, ’Ford Foundation’, ’Silicon
Valley Community Foundation’.

Top 10 largest political parties and their
acronyms151515List_of_largest_political_parties: ’Bharatiya Janata Party’,
’Communist Party of China’, ’Democratic Party’, ’Republican Party’, ’Justice
and Development Party’, ’Aam Aadmi Party’, ’Pakistan Tehreek-e-Insaf’, ’Chama
Cha Mapinduzi’, ’United Socialist Party of Venezuela’, "Cambodian People’s
Party".

And some of their acronyms: ’BJP’, ’CPC’, ’CCP’, ’AKP’, ’AAP’, ’TPI’, ’CCM’,
’CPP’.

A few well known universities: ’Harvard University’, ’Stanford University’,
’University of Cambridge’, ’Massachusetts Institute of Technology’,
’University of California, Berkeley’, ’Princeton University’, ’Columbia
University’, ’California Institute of Technology’, ’University of Oxford’,
’University of Chicago’

And some of their short names and acronyms: ’Harvard’, ’Stanford’,
’Cambridge’, ’Berkeley’, ’Princeton’, ’Columbia’, ’Oxford’, ’Chicago’, ’Cal’,
’U of C’.

Obviously many of these names did not pass the ambiguity requirement of having
multiple wikipedia entities.

##  Appendix B Good sentences

In Section 2.2 we used a notion of a ’good sentence’ for sake of the Entities
dataset filtering. In this context, a ’good sentence’ is a sentence satisfying
the following requirements:

  1. 1.

The sentence does not contain the strings ’==’ and newlines.

  2. 2.

The sentence has the number of words not less than 4, and the number of
characters between 20 and 1000.

  3. 3.

The first word of the sentence is ’alpha’, i.e. it consists of the
alphabetical characters.

  4. 4.

The fraction of the ’alpha’ words in the sentence is not lower than 0.6.

##  Appendix C Filtering of news

The news texts obtained by the initial search (as explained in Section 2.4)
went through the initial filtering as follows:

  1. 1.

The name of the mention in the text must strongly overlap with at least some
entity from the Entities dataset.

  2. 2.

The number of characters [‘*’, ‘#’, ‘&’] in the text must be not higher than
2. The reason is that these characters are often used for bullets, and the
fraction of varied listings (sport, TV, business) in random news is high.

  3. 3.

Fraction of non-alpha characters in the text must be not higher than 0.3. The
reason, similar to above, is to remove business documents or texts filled with
sport scores.

This still left more than half million news texts (each with a mention of
interest). Additional filtering is done for sake of manageable labeling: (1)
keeping only texts with keeping only texts the length of between 500 and 3000
characters, and (2) keeping only texts with mentions that can be confused with
only 3-10 Wikipedia entities. This filtering step still left more than 17K
news texts. Finally, the number was reduced to the ’best quality’ 1000 news
texts by the following filtering:

  1. 1.

Removing texts with containing the strings: ’wedding’, ’service will be held’,
’leaves to cherish’, ’died peacefully’, ’marriage’, ’annual’, ’passed away’,
’survived by’, ’preceded in death’. The reason for this is to reduce the
fraction of names that do not exist in the Entities dataset but have the same
or similar names. Having such samples is important, but we want also to have a
good fraction of entities from random news that do belong to our Entities
dataset.

  2. 2.

Removing texts which had, after NLTK sentence tokenization, average length of
sentence less than 60 characters. The reason is to remove texts containing
long listings; a normal average news sentence is not so short.

  3. 3.

Removing texts with fraction of newline characters higher than 1%.

  4. 4.

Removing texts containing the strings: ’http’, ’www.’, ’.com’, ’**’, ’[’, ’{’,
” or ’#’. The reason is to filter out texts with advertisements, and texts on
obscure subjects from obscure sources.

  5. 5.

Sorting the remaining (less than 2000) texts by count of non-alpha and non-
digit symbols and selecting the 1000 cleanest.

##  Appendix D Filtering of backlinks

The filtering and cleaning of backlinks texts (Section 2.5) is done as the
following.

  1. 1.

Removing Wikipedia texts that have titles starting with: ’Book’, ’Category’,
’Draft’, ’File’, ’Help’, ’List’, ’MediaWiki’, ’Portal’, ’Special’, ’Talk’,
’Template’, ’User’, ’WikiProject’, ’Wikipedia’.

  2. 2.

Cutting any Wikipedia text starting from any section named as: ’Bibliography’,
’Discography’, ’External Links’, ’Filmography’, ’Footnotes’, ’Further
Reading’, ’Notes’, ’References’, ’See Also’.

  3. 3.

Removing all mentions occurring in ’bad’ text locations. A ’bad’ location
means that a piece of text in between 100 characters before and 100 characters
after the mention does not satisfy the following conditions:

    1. (a)

Fraction of digits must not exceed max 0.05 of all the characters.

    2. (b)

Fraction of alpha-characters must not be below min 0.8.

    3. (c)

Fraction of newlines must not exceed max 0.01.

  4. 4.

Cutting the text starting from 1000 characters down from the lowest occurring
mention.

The ’removing’ of a mention means that the mention looses its link notations,
and becomes simple word (or words) in the text.

##  Appendix E Mention-Entities Ambiguity

###  E.1 Entities

In order to characterize ambiguity of the named entities in a dataset, we
suggested and described a ’mention-entities overlap’ in Section 3. For
clarity, here we define the overlap.

For a single dataset, for example Entities, as in Section 3.1, we have $M$
entities, each entity is having its own text $T_{i},i=1,2,...,M$. Each text
$T_{i}$ has a list $T_{i}^{(s)}$ of mentions $u_{\alpha}$ that were tagged
"Same", and a list $T_{i}^{(o)}$ of mentions $v_{\alpha}$ that were tagged
"Other". In each "Same" list $T_{i}^{(s)}$ we will also include the ’official’
name of the entity (the title of the corresponding Wikipedia page) $t_{i}$.
For example, the "Same" lists of the first two texts:

$T_{1}^{(s)}=[t_{1},u_{1},...,u_{N_{1}^{(s)}}]$ (1)
$T_{2}^{(s)}=[t_{2},u_{N_{1}^{(s)}+1},...,u_{N_{2}^{(s)}}]$ (2)

Similarly, the "Other" lists of mentions:

$T_{i}^{(o)}=[v_{N_{i-1}^{(o)}+1},...,v_{N_{i}}^{(o)}]$ (3)

Here $N_{0}^{(o)}=0$ and $N_{0}^{(s)}=0$. Of course some "Other" lists can be
empty.

For example, our entity "Milton, Indiana" has three mentions in its text:
"Milton" (Same), "Milton" (Other), "Milton" (Same). Its list $T^{(s)}$ is
["Milton, Indiana", "Milton", "Milton"], and its list $T^{(o)}$ is ["Milton"].
The entity "David Jones (footballer, born 1940)" has eight mentions, first one
is "David Willmott Llewellyn Jones", and the other seven are all "Jones".
Since all these mentions are tagged "Same", they all (and the title) go into
$T^{(s)}$, and $T^{(o)}$ is empty.

We define the mention-entities ambiguity $C^{(s)}$ for the "Same" mentions as:

$C^{(s)}=\frac{1}{N_{M}^{(s)}}\sum_{\alpha=1}^{N_{M}^{(s)}}|\\{i:u_{\alpha}\in
T_{i}^{(s)}\\}|$ (4)

Here $|\\{i:u_{\alpha}\in T_{i}^{(s)}\\}|$ is the number of all the entities
$i$ that had at least one mention $u_{\alpha}$ (aka string, ’surface form’
occurrence) tagged "Same". Similarly, the mention-entities ambiguity $C^{(o)}$
for the "Other" mentions is:

$C^{(o)}=\frac{1}{N_{M}^{(o)}}\sum_{\alpha=1}^{N_{M}^{(o)}}|\\{i:v_{\alpha}\in
T_{i}^{(s)}\\}|$ (5)

Generally, for any dataset that has known correct mentions of entities (in our
Entities dataset they are tagged as "Same"), and for any kind $o$ of mentions
$v_{\alpha}$ of interest, we can define the ambiguity by the equation 5.

In our Entities dataset, the mention-entities ambiguity is 181.3 for "Same",
and 20.9 for "Other".

###  E.2 News and Backlinks to Entities

In Appendix E.1 we considered ambiguity of mentions from the same dataset
(e.g. Entities). Here we are considering ambiguity of mentions in one dataset
$D_{1}$ (in our case News or Backlinks) with respect to entities of another
dataset $D_{2}$ (in our case Entities).

We can apply the same definition by the equation 5, with an understanding that
the lists $T_{i}^{(s)}$ are from $D_{2}$, but the summation is done over the
mentions $v_{\alpha}$ from $D_{1}$:

$C^{(o)}=\frac{1}{N^{(o)}}\sum_{\alpha=1}^{N^{(o)}}|\\{i:v_{\alpha}\in
T_{i}^{(s)}\\}|$ (6)

Here $N^{(o)}$ is simply the number of the mentions of interest in $D_{1}$.

For the 724 News mentions that were not tagged as one of entities of Entities,
the ambiguity $C^{(o)}=1.6$. A caveat here is that, while the averaging in the
equation 6 is done over all the 724 mentions, the ambiguity is actually
created by 77% of these mentions (555 mentions) that do exist in one or more
lists $T_{i}^{(s)}$. The remaining 23%, while having similar names, do not
exactly match the mentions of the Entities texts.

For the 276 News mentions that were tagged as the entities of Entities, we
have to add each mention to the list $T_{i}^{(s)}$ of the entity with which
the mention was linked (by the annotators). With or without taking this into
account, the ambiguity $C^{(o)}=1.9$ (the difference is only about 2%).

For the 29019 Backlinks mentions the ambiguity $C^{(o)}=7.6$.


$\Pi_{\Sigma}(x) = \Pi_{\Sigma}(y) = \varepsilon$
$(p,q,1) \xrightarrow{a} (p',q',1)$

We will now show that $B$ accepts precisely the set of words that have multiple parsings
in $\TParse_h$.

$w \in \dom{h}\setminus\udom{h}$ iff $B$ has an accepting run on $w$.

Suppose that $B$ has an accepting run on $w$.
Then, by our construction, $T_h^o$ has two accepting runs $\alpha$ and $\beta$, such
that $\alpha \neq \beta$ and $\Pi_{\Sigma}(\alpha) = \Pi_{\Sigma}(\beta) = w$.
This in turn means that $\TParse_h$ has two runs reading $w$ and producing $\alpha$ and
$\beta$ respectively. Therefore, $\alpha,\beta\in\Parse_{h}(w)$ and we get

Conversely, suppose that $w\in\dom{h}\setminus\udom{h}
=\dom{\Parse_{h}}\setminus\fdom{\Parse_{h}}$.  Let $\alpha,\beta\in\Parse_{h}(w)$ with
$\alpha\neq\beta$.  Then, $\TParse_h$ has two runs reading $w$ and producing $\alpha$
and $\beta$ respectively.  By Theorem <ref> we have
$\Pi_{\Sigma}(\alpha) =\Pi_{\Sigma}(\beta) =w$.  Hence, we can write $w = a_1 a_2 \cdots
a_n$, $\alpha = u_0 a_1 u_1 \cdots a_n u_n$, and $\beta = v_0 a_1 v_1 \cdots a_n v_n$,
where $\Pi_{\Sigma}(u_i) = \Pi_{\Sigma}(v_i) = \varepsilon$, for $0 \leq i \leq n$.
Further, let $i$ be the least index such that $u_i \neq v_i$.  From the construction, we
know that after reading $a_{1}\cdots a_{i}$,
the automaton $B$ reaches a state $(p,q,0)$ (by using rule (1) repeatedly).
If $i = n$, then $(p,q,0)\in F$ and $B$ accepts $w$.
If $i<n$, then $B$ uses the rule (2) to go to a state $(p',q',1)$ when reading $a_{i+1}$.
Then, we can use repeatedly rule (3) to read $a_{i+2}\cdots a_n$
and reach a state in $F$.
In both cases, $B$ has an accepting run on $w$.

Note that the number of states of $B$ is $2\norm{\TParse_h}^2$, where $\norm{\TParse_h}$
denotes the number of states of $\TParse_h$.  From Theorem <ref>, we
know that $\norm{\TParse_h}\leq|h|^{\w{h}}$ for general and
$\norm{\TParse_h}\leq|h|$ when $h$ does not use Hadamard product, $k$-star or reverse $k$-star.  Thus, the number of states of $B$ is at most $2|h|^{2\cdot\w{h}}$ in general,
and $2|h|^2$ when $h$ does not use Hadamard product, $k$-star or reverse $k$-star.
Moreover, the construction takes time
$\poly{(\norm{\TParse_h})}$, which is
for general and $\poly{(|h|)}$
when $h$ does not use Hadamard product, $k$-star or reverse $k$-star.

Using Lemma <ref> on $B$, we obtain a reversible automaton $B'$ with number
of states $2\cdot 2^{|h|^{2\cdot\w{h}})}+6$ that accepts the complement of $L(B)$, i.e.,
$B'$ accepts the set of words having at most one parsing $h$.
Using Lemma <ref> on $\TParse_h$, we obtain a uniformizing
2RFT $\TParse'_h$ of size $2^{\mathcal{O}(|h|^{\w{h}})}$.

Let $\TParse^{U}_{h}$ be defined as the 2RFT that first runs the automaton $B'$ without
producing anything, then runs $\TParse'_h$ if $B'$ has accepted.  This transducer is
reversible since it is the sequential composition of reversible transducers, and computes
the parsing relation on words belonging to the intersection of the domain of the two
machines, i.e., $\udom{h}$ the set of words having exactly one parsing.  Its number of
states is the sum of the number of states of the two machines ($+1$ dummy state making the
transition), hence $\norm{\TParse^{U}_{h}}=2^{\mathcal{O}(|h|^{2\cdot\w{h}})}$.

Thanks to Theorem <ref>, for any given $h$, we have the evaluator
2RFT $\T_h$ which, when composed with the parsing relation $\Parse_{h}$, computes the
relational semantics of $h$: $\rsem{h}=\sem{\T_h}\circ\Parse_h$.  Let $\T^{U}_{h}$ be the
2RFT obtained by the composition of $\T_h$ and $\TParse^{U}_{h}$ (which restricts the
parser to the unambiguous domain of $h$), i.e., $\T^{U}_{h} = \T_{h}\circ\TParse^{U}_{h}$.
Then, $\T^{U}_{h}$ computes the unambiguous semantics of $h$: $\usem{h}=\sem{\T^{U}_h}$.

Recall that the number of states of the evaluator is
$\norm{\T_{h}}=\mathcal{O}(|h|\cdot\w{h})$.  Then, as the composition of 2RFTs can be done
with polynomial blowup, we get $\T^{U}_{h}$ whose number of states is
Note that, if $h$ does not use Hadamard, $k$-star or reverse $k$-star, then both
$\norm{\TParse_h}$ and $\norm{\T_h}$ are linear in $|h|$.  As a consequence, for an RTE
$h$ belonging to this fragment, we get $\T^{U}_{h}$ whose number of states is

§ CONCLUSION

We conclude with some interesting avenues for future work.  An immediate future work is to
adapt our parser-evaluator construction to work for . We believe that this can be
done with some effort, preserving our complexity bounds.  Note that in this paper, we have
already done the work to handle $\kstar{k}{e}{f}$ even though 2-star was sufficient for
; it remains to ensure the aperiodicity of the parser-evaluator, preserving our
complexity bounds, to make our construction work for . Another interesting question
is to see if our approach and construction can be made amenable for extended , which
also allows function composition as an operator of the syntax.  Note that this does not
increase expressiveness, but is a useful shorthand.
Already in this paper, we have
considered some useful functions like duplicate and reverse along with the fragment
[, $\reverse$]; allowing function composition makes the use of these shorthands
As we construct reversible machines, composing them is effective and hence having composition as the topmost operator is straight-forward. However, using composition as an operator would require the parsing of intermediate outputs which we leave as an open problem.

[1]
Rajeev Alur, Loris D'Antoni, and Mukund Raghothaman.
DReX: A declarative language for efficiently evaluating regular
string transformations.
In POPL, pages 125–137. ACM, 2015.

[2]
Rajeev Alur, Adam Freilich, and Mukund Raghothaman.
Regular combinators for string transformations.
In CSL-LICS, pages 9:1–9:10. ACM, 2014.

[3]
Nicolas Baudru and Pierre-Alain Reynier.
From two-way transducers to regular function expressions.
In DLT, volume 11088 of Lecture Notes in Computer
Science, pages 96–108. Springer, 2018.

[4]
Nicolas Baudru and Pierre-Alain Reynier.
From two-way transducers to regular function expressions.
Int. J. Found. Comput. Sci., 31(6):843–873, 2020.

[5]
Bruno Courcelle.
Monadic second-order definable graph transductions: A survey.
Theor. Comput. Sci., 126(1):53–75, 1994.

[6]
Luc Dartois, Paulin Fournier, Ismaël Jecker, and Nathan Lhote.
On reversible transducers.
In ICALP, volume 80 of LIPIcs, pages 113:1–113:12.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.

[7]
Luc Dartois, Paul Gastin, and Shankara Narayanan Krishna.
SD-regular transducer expressions for aperiodic transformations.
In LICS, pages 1–13. IEEE, 2021.

[8]
Vrunda Dave, Paul Gastin, and Shankara Narayanan Krishna.
Regular transducer expressions for regular transformations.
In LICS, pages 315–324. ACM, 2018.

[9]
Vrunda Dave, Paul Gastin, and Shankara Narayanan Krishna.
Regular transducer expressions for regular transformations.
Inf. Comput., 282:104655, 2022.

[10]
Joost Engelfriet and Hendrik Jan Hoogeboom.
MSO definable string transductions and two-way finite-state
ACM Trans. Comput. Log., 2(2):216–254, 2001.

[11]
Attila Kondacs and John Watrous.
On the power of quantum finite state automata.
In FOCS, pages 66–75. IEEE Computer Society, 1997.

[12]
Jacques Sakarovitch.
Elements of Automata Theory.
Cambridge University Press, 2009.

[13]
Marcel-Paul Schützenberger.
Sur certaines opérations de fermeture dans les langages rationnels.
In Symposia Mathematica, Vol. XV (Convegno di Informatica
Teorica, INDAM, Roma, 1973), pages 245–253. Academic Press, 1975.