# API-Assisted Code Generation for
Question Answering on Varied Table Structures

Yihan Cao Shuyi Chen∗ Ryan Liu∗
Zhiruo Wang Daniel Fried
Carnegie Mellon University
<EMAIL_ADDRESS>Equal contribution.

###### Abstract

A persistent challenge to table question answering (TableQA) by generating
executable programs has been adapting to varied table structures, typically
requiring domain-specific logical forms. In response, this paper introduces a
unified TableQA framework that: (1) provides a unified representation for
structured tables as multi-index Pandas data frames, (2) uses Python as a
powerful querying language, and (3) uses few-shot prompting to translate NL
questions into Python programs, which are executable on Pandas data frames.
Furthermore, to answer complex relational questions with extended program
functionality and external knowledge, our framework allows customized APIs
that Python programs can call. We experiment with four TableQA datasets that
involve tables of different structures — relational, multi-table, and
hierarchical matrix shapes — and achieve prominent improvements over past
state-of-the-art systems. In ablation studies, we (1) show benefits from our
multi-index representation and APIs over baselines that use only an LLM, and
(2) demonstrate that our approach is modular and can incorporate additional
APIs.

##  1 Introduction

Figure 1: Our approach answers questions about complex tables by representing
the tables as a Pandas multi-index data frame, and using a code generation LM
to translate the question into a Python program that uses assistant API
functions to operate on the data frame.

Tables are an important and widely used format for storing and retrieving
information. However, since they are often constructed to present information
in a visually effective way, they consequently occur in diverse formats (Chen
and Cafarella, 2013; Nishida et al., 2017; Wang et al., 2021b). Thus, to
effectively answer questions about all tabular information, we must consider
information stored in relational (Pasupat and Liang, 2015), matrix, and
hierarchically indexed tables (Cheng et al., 2022), and also address scenarios
where multiple tables are presented conjointly (Yu et al., 2018).

In the past, works have focused on achieving strong results on datasets with
particular table structures and required tailoring logical forms to each
specific type of table structure (Wang et al., 2015; Guo et al., 2019). These
methods struggle to work on tables with structures outside of their original
domain. For example, the neural-symbolic machine (NSM) approach designed for
relational tables (Liang et al., 2017) only achieves 29.2% accuracy on the
hierarchical matrix table dataset HiTab Cheng et al. (2022) due to the
ineffectiveness of its logical forms on hierarchical tables.

Our work focuses on developing a unified framework to solve TableQA tasks
across diverse table structures using Python as an intermediate language. In
contrast with previous approaches that use custom logical forms to query table
data (Guo et al., 2019; Cheng et al., 2022), we propose to query entries and
perform operations within the widely used Python Pandas library. This allows
us to leverage the strong few-shot Python generation capabilities of large
code generation models, whilst saving costs by using only a few training
examples. An overview of the framework is presented in Figure 1, with more
details in Figure 3. Our framework consists of three main parts:

First, we transform tables with varied structures into a unified multi-index
data frame representation adopted from the Python Pandas library (§3.1). The
multi-index objects can effectively retain the structural information in a
wide range of table formats. From the implicit first step illustration in
Figure 1 and more detailed one in 2(c), we convert tables from a hierarchical
format to the multi-index representation, which will enable generated code to
successfully query elements in the table.

Second, we translate TableQA questions into Python programs as an executable
intermediate language by prompting code generation models (§3.2).
Specifically, we use a few-shot paradigm where we provide the multi-index
headers of the table, a few rows of the table in textual form, the question,
and exemplar program annotations. As shown in Figure 1, the table and question
are input to the code generation model along with the few-shot prompt, and the
generated Python code uses the Pandas data.loc function to query the
appropriate cells.

Third, we introduce assistant API functions to extend the capabilities of our
framework beyond Python Pandas and achieve broader coverage over various
TableQA tasks. These functions enable a model-generated program to query
external knowledge and perform various additional operations on the multi-
index representation. In this paper, we demonstrate the usage of two simple
types of API functions, Operation APIs and QA API (§3.3), and show through
ablations that they increase the performance of our framework across various
datasets. For example in Figure 1, the model outputs code using one of our API
functions, compare_larger, to solve the question.

We evaluate our method across relational, hierarchical, and matrix tables, as
well as multiple table paradigms using the WikiTableQuestions (WikiTQ) Pasupat
and Liang (2015), HiTab Cheng et al. (2022), AIT-QA Katsis et al. (2022), and
Spider Yu et al. (2018) datasets (§4). For code generation models, we use a
more capable proprietary model, Codex Chen et al. (2021), and an open-source
model, StarCoder Li et al. (2023). We find that our framework surpasses the
state-of-the-art few-shot baselines on the HiTab, AIT, and Spider datasets,
achieving absolute improvements of 24.5%, 26.2%, and 2.3%, respectively, while
retaining non-trivial performance on WikiTQ. Furthermore, we perform an
ablation study on the API functions we introduced and find that they bring
significant improvements across datasets and models. Our framework also allows
the use of existing API operations within Pandas in a modular way. For
example, we show that combining Pandas’ SQL interface API with our multi-index
representation and APIs improves performance by 3.7–7.6% on relational
datasets.

##  2 Problem Setting and Datasets

In this section, we provide a formal description of the TableQA tasks (§2.1)
and describe the four datasets used in our experiments, containing tables of
varied structures (§2.2).

###  2.1 Problem Statement

Each example in a TableQA task contains a table $t$ and a question $q$ about
the table, and aims to generate the correct answer $a$ to the question. While
both $q$ and $a$ are textual sequences, the table $t$ can vary in structure —
from relational tables (2(a), 2(b)) to hierarchical matrix tables (2(c)).

The common symbolic approach to TableQA generates an intermediate program $p$
from a model $M$ using the table and question, $p=M(q,t)$. The program is then
executed on $t$ to yield the answer $a^{\prime}=exec(p,t)$. In traditional
methods, tables are serialized to text sequences by cell string concatenation,
and programs are logical forms specifically designed for certain domains. To
preserve and leverage more structural information, we represent tables as
Pandas multi-index objects, $t_{m}$, and generate Python programs accordingly.

###  2.2 QA over Varied Table Structures

Dataset | Size | Table Info
---|---|---
dev | test | structure | source
WikiTQ Pasupat and Liang (2015) | 2,381 | 4,344 | relational, single | Wikipedia
HiTab Cheng et al. (2022) | 1,671 | 1,584 | hierarchical matrix | Stat. reports, Wikipedia
AIT-QA Katsis et al. (2022) | — | 515 | hierarchical | Airline documents
Spider Yu et al. (2018) | 1,034 | — | relational, multiple | College data, WikiSQL

  * •

* Spider has an undisclosed online test set.

  * •

** We treat the entire AIT-QA dataset as a single test set in our evaluations.

Table 1: Statistics and properties of the datasets we use to evaluate our
approach, encompassing varied table structures and sources.

We use four diverse TableQA datasets to evaluate our approach: WikiTQ Pasupat
and Liang (2015), HiTab Cheng et al. (2022), AIT-QA Katsis et al. (2022), and
Spider Yu et al. (2018). As listed in Table 1, these datasets cover a broad
spectrum of table structures and topical domains, thereby presenting various
challenges associated with different table structures.

#### WikiTableQuestions (WikiTQ)

WikiTQ (Pasupat and Liang, 2015) contains relational tables with relatively
simple structures. All tables are collected from Wikipedia articles. The
questions usually involve basic arithmetic operations, such as sum and max,
and sometimes require compositional reasoning over table entries. Since our
method does not require any training, we use the standard validation set and
test set with 2,381 and 4,344 samples.

#### HiTab

Cheng et al. (2022) involves hierarchical matrix tables collected from
statistical reports and Wikipedia articles, covering diverse domains such as
economics, education, health, science, and more. HiTab challenges existing
methods with its broad set of operations, complex table structures, and
diverse domain coverage. It contains 3,597 hierarchical tables with 10,672
questions. We evaluate on their test set containing 1,584 samples.

(a) A relational table.

(b) A multi-table relation.

(c) A hierarchical matrix table parsed into a multi-index object: step (1)
transforms table headers into a tree representation, and step (2) creates a
Pandas multi-index object.

Figure 2: Examples of diversely structured tables.

#### AIT-QA

Katsis et al. (2022) contains tables and questions that particularly focus on
the airline industry domain. It also contains tables with complex structures
such as hierarchical headers or bi-dimensional matrix shapes. Both the complex
structure and domain-specific terminology are challenging for TableQA tasks
(Zhu et al., 2021; Katsis et al., 2022). AIT-QA contains 515 questions that
are distributed across 116 tables. We use all 515 questions as the test set
for evaluation purposes.

#### Spider

Yu et al. (2018) is a multi-domain text-to-SQL benchmark with tables in a
database format. It contains 200 databases across 138 different domains. All
“databases” in Spider consist of multiple relational tables connected by
primary / foreign keys, which poses a unique challenge for methods – the
multi-table structure. Evaluations on the hidden test set are supported by its
online benchmark which only accepts SQL programs. We instead evaluate on the
validation set containing 1,034 questions.

##  3 Method

Figure 3: Our framework consists of three stages: (1) Multi-index parsing
accepts one or more tables with diverse table structures, and transforms them
into a single hierarchical table, represented using a Pandas multi-index
representation $m$ (a process described in §3.1). (2) We then provide a
natural language question, in-context exemplar annotations, and multi-index
representation $m$ as a prompt for pretrained code models like Codex or
StarCoder for Python code generation, as described in §3.2 and §3.3. The
prompt specifies examples of using our QA API and operation APIs. (3) Finally,
we execute the Python code, which could contain QA or operation APIs, on the
Pandas data frame, outputting the final results. Our API definitions are given
in Figure 5 and Figure 4.

We first describe our approach for representing variously structured tables
with a unified multi-index format (§3.1). We then introduce our method to
answer TableQA questions by generating Python programs (§3.2) from a code LLM.
Lastly, we detail the use of custom helper API functions (§3.3) that are
learned to be used by the LLM in context (§3.4). Figure 3 gives an overview of
our method.

###  3.1 Unifying Representation of Diverse Table Structures with Multi-Index
Parsing

To represent diverse table structures in a unified way that is naturally
compatible with Python programs, we propose to transform any table with
varying structures, denoted as $t$, into a Pandas multi-index
representation,111https://pandas.pydata.org/docs/reference/api/pandas.MultiIndex.html
$m$. We denote this process as multi-index parsing, which first converts a raw
table $t$ to a bi-dimensional tree structure $b=(T,L,V)$, then parses it into
a multi-index representation $m$. The two steps are illustrated in 2(c).

First, we first transform a table $t$ of any structure into a bi-dimensional
tree representation $b=(T,L,V)$ as defined by Wang et al. (2021b). It yields
two coordinate trees: (i) the left tree $L$ by indexing the values $V$ from
the left header, and (ii) the top tree $T$ by indexing data cells $V$ from the
top header. Specifically in the example 2(c), $T$ represents the deep blue
area (i.e., two rows at the top); $L$ represents the first column to the left;
and $V$ covers all the data cells from $10,000$ from the top-left to $0.2\%$
to the bottom right.

Algorithm 1 Preorder tree traversal for multi-indexing.

$result\leftarrow list()$

$tempList\leftarrow list()$

procedure preorder($p$: coordinate tree node, $result$, $tup$)

if $p$ is not tree root then

$tempList\leftarrow tempList+(p.value,)$

end if

if $p.index$ is None then

$results\leftarrow results+tempList$

end if

for $child$ in $p.children$ do preorder($child$, $result$, $tempList$)

end for

return $result$

end procedure

Next, we traverse the left and top trees and extract header path tuples from
both header trees to define the row indexes and column indexes in the multi-
index representation $m$, which can be used to reconstruct the original table
using Pandas semantics. Specifically, we use a preorder traversal (as
illustrated in Algorithm 1) on both the top tree $T$ and the left tree $L$,
and enumerate all paths starting from the root node to each leaf header node.
For every such root-to-leaf path, we aggregate all cell strings along the path
into a tuple. For each header tree, we collect all such tuples and
correspondingly define the row/column index list in the multi-index
representation $m$. For example, for the top header in 2(c), Illness
$\rightarrow$ Cold $\rightarrow$ total is one possible top header path, then
we add (Illness, Cold, total) to the column index list in $m$.

Note that this multi-index parsing process can be readily applied to tables of
diverse structures, with a unified representation efficiently preserving all
structural information. In the special case of simple-structured tables such
as flat relational tables, both the top and left headers are represented by
single-layer trees and undergo a similar parsing process as hierarchical
structures. When dealing with questions that involve multiple tables, we
convert all tables into multi-index objects, feed them to the model, and let
the model choose which parts it will use to answer the question. For more
detailed illustrations of this parsing process for tables of different
structures, please refer to §D.

###  3.2 Generating Python Programs

With table environments represented as multi-index representation $m$, we
generate Python programs $p$ to execute on $m$ to yield the answer prediction
$a^{\prime}$. Our method is general and not tied to any particular code
generation model, as long as the model has sufficient natural language
understanding and code generation capability. As such, we validate our
approach using two code language models (code LMs) for Python program
generation: the proprietary Codex model (Chen et al., 2021) and the open-
source StarCoder model (Li et al., 2023).

Codex is a code LM based on GPT-3 (Chen et al., 2021). We access it through
OpenAI API calls.222One can call the Codex model via API without knowing the
internal process or model parameters. We experiment with the strongest version
davinci-002 with $175B$ parameters. StarCoder is an open-source $15B$ code LM,
which at the time of this writing achieved top performance among open-source
models on many code generation benchmarks such as HumanEval Li et al. (2023).
Both models are trained on a mixture of natural language and code sequences.
We generate code from both models using few-shot prompting (Brown et al.,
2020), with prompts specifying examples of the mapping from natural language
questions and tables to Python Pandas code. More details follow in §3.4.

###  3.3 Incorporating Assistant APIs

We describe two types of API functions, Question Answering (QA) APIs and
Operation APIs, to expand the ability of code LMs to incorporate external
knowledge and extra table operations.

#### Operation APIs

Operation APIs are designed to enhance the functionality of LM-generated
programs. Since we use Python as the query language and represent tables in
Pandas, we are able to incorporate simple Python APIs into the solution. For
demonstration, we employ two simple comparison APIs in this paper. We
emphasize that our framework is not tied to any specific operation API, and
therefore offers flexibility in designing customized APIs for different
datasets or question types.

Figure 4: Illustration of the two comparison operation APIs.

The design of the comparison APIs is inspired by the empirical observation
that Codex is better at handling numerical questions, such as “what is the age
of Person A?”, than qualitative questions like “which is higher, A or B?”. We
design two comparison APIs, as shown in Figure 4, to address this issue. Each
API takes a list of values and a list of indices and returns the largest or
the smallest index according to the values. An example showing how the
comparison APIs are used is shown in Figure 1. We find in §5 that the
additional operations enabled by these APIs substantially improve performance.

#### QA API

Sometimes TableQA questions require external knowledge which is not included
in the given table. The QA API, proposed by Cheng et al. (2023), is designed
to access external knowledge when solving table QA tasks, by making calls to
an LLM.

Figure 5: Illustration of the question answering API.

As illustrated in Figure 5, during the table question answering stage, we
prompt the LLM to write questions itself. These generated questions will
direct the code parsing program to call the QA API function. The QA API takes
in this question and a set of table indices as parameters. For each value in
the questioned column, we insert the value into the generated question and
prompt the model again to give an answer to this question. Then, we select the
rows with true values in the returned column. We include a real case from
HiTab Cheng et al. (2022) in Figure 11 which requires geographical knowledge
to accurately answer the question.

###  3.4 Learning APIs In Context

Building upon the in-context learning ability of large language models (Brown
et al., 2020), we use examples of API usage as a few-shot context for LM
generation of programs. Our LM prompt is designed to be a mixture of
instructions and solution examples. The instructions specify API usage
guidelines and scenarios in which it should be used. The solution examples
incorporate a balanced mix of examples, some of which utilize the assistant
API to perform tasks, while others tackle the question with Pandas semantics
directly. With this diversity of input examples, we aim to encourage the usage
of the assistant APIs in the code generated by the LMs, while avoiding over-
reliance on some APIs. Refer to §B for more complete prompt templates we used
for different datasets.

##  4 Experiments

In this section, we first introduce the experiment (§4.1) and evaluation
settings (§4.2), then present our results and analysis (§4.3). We also test
the robustness of our method with different code models (§4.4) and
intermediate query language forms (§4.5).

###  4.1 Implementation Details

We use the StarCoder 16$B$ and code-davinci-002 (Codex) models to generate
Python programs. We set the sampling temperature to $0.7$ for both models. For
every question, we generate five model predictions and select the candidate
with the highest log probability. We include five shots in the prompt for
WikiTQ, HiTab, and Spider datasets, and eight shots for the AIT dataset.

###  4.2 Evaluation Metrics

We evaluate performance using the Execution Accuracy (EA) metric following
Pourreza and Rafiei (2023) and Cheng et al. (2023). EA measures the percentage
of questions for which our method produces programs that yield correct
answers. We did not include exact matching (EM) as the measure to determine if
the predicted query is equivalent to the gold query, since it can lead to
false negative evaluations when the semantic parser generates novel syntax
structures Pourreza and Rafiei (2023); Yu et al. (2018). Moreover, as Python
is our main query and API function language and most datasets do not provide
golden queries in Python, EM is not a practical measure in our case.

###  4.3 Experiment Results

footnote 4 shows our main experiment results across the datasets described in
§2.2, encompassing varied table structures, using the Codex (code-davinci-002)
code LM. We compare our full method (Ours) with an ablated version (Codex)
that only uses few-shot prompting of the code LM, without including our multi-
index structure and API functions (see §5.2 for details and more ablations).
We also give the performance of state-of-the-art baselines for each dataset
from past work.

Dataset | HiTab | Spider | AIT-QA | WikiTQ
---|---|---|---|---
Baseline | MAPO | DIN-SQL | RCI | BINDER
40.7 | 61.5 | 51.8 | 54.8
Codex | 59.6 | 61.2 | 77.8 | 41.7
w/ API | 69.3 | 63.8 | 78.0 | 42.4
(Ours)

Table 2: Execution accuracy on four TableQA dataset with Codex generated
programs, in comparison to state-of-the-art baselines: the MAPO Liang et al.
(2018) baseline from HiTab (Cheng et al., 2022), DIN-SQL (Pourreza and Rafiei,
2023) for Spider, RCI (Glass et al., 2021) for AIT-QA, and BINDER (Cheng et
al., 2023).444For a fair comparison with our approach, we use 5-shot prompting
for BINDER rather than the 12-shot experiments in Binder et al. (2022), which
decreases performance compared to the results in their paper.

Our approach, which uses a unified representation for tables and question
semantics, typically improves over past work despite their use of
representations tailored to individual datasets. In particular, our approach
obtains an improvement of 28.6% over the past state-of-the-art training-based
method Liang et al. (2018), and a 9.7% improvement on plain few-shot prompted
Codex models for the HiTab dataset.

One exception is the WikiTQ dataset, where our method underperforms the BINDER
approach (Cheng et al., 2023). We attribute this to the superior alignment of
BINDER’s API with the question characteristics of the WikiTQ dataset, which
includes many questions that require external knowledge.

Meanwhile, we find strong performance from using Python as a QA representation
of the code LM alone: in particular, on the HiTab dataset, we see that the
Codex model already achieves an 18.9% improvement compared to previous
training-based methods Liang et al. (2018).

###  4.4 Robustness to Code Generation Model

We next analyze method performance when using the recently released open-
source code generation model StarCoder-16B Li et al. (2023). The findings are
compiled and presented in Table 3.

While the base model performance with StarCoder is lower than Codex, we still
observe an improvement from our generated API across all settings, with a
substantial improvement on the AIT-QA dataset, presumably because a large
portion of the questions in AIT-QA can be more easily solved using our API
functions. This indicates that our approach is compatible with a range of code
generation LMs, and performance may scale with future improvements in open-
source code LMs.

Dataset | HiTab | AIT-QA | WikiTQ
---|---|---|---
StarCoder | 29.0 |  4.0 | 22.4
w/ API | 30.1 | 26.1 | 23.2

Table 3: Execution accuracy on four TableQA datasets with StarCoder generated
programs.

###  4.5 Robustness to Intermediate Forms

One feature of our Python and Pandas-based method for TableQA is that it is
modular, and can use existing API methods from other Python libraries when
appropriate. In this section, we perform a case study where we use the SQL
querying API of the pandasql extension library for
Pandas.555https://pypi.org/project/pandasql/ We experiment with the WikiTQ
dataset since all tables within are relational types, the operations on which
can be readily covered by the SQL grammar.

Similarly to the in-context learning configuration introduced in §3.2, we
adapt our input to prompt the model to generate SQL queries. An example prompt
is shown in Figure 6.

Figure 6: An example prompt for a model to generate SQL queries on the WikiTQ
dataset.

The generated SQL queries are executed on Pandas data frames and return Python
objects, hence, we can still retain our same API functions and multi-index
data frame representation. Please find more details about the prompt and code
in §C.

Code Model | Query Language
---|---
Python | w/ API | SQL | w/ API
StarCoder | 15.6 | 15.6 | 22.4 | 23.2
Codex | 41.7 | 42.4 | 45.4 | 46.7

Table 4: Execution accuracy on WikiTQ when generating Python and SQL programs.

The experimental results with and without the SQL API are presented in Table
4. We see that SQL outperforms Python on the WikiTQ dataset, which we suspect
is because this relational dataset affords short SQL queries, which are easier
to generate than long Python functions for code LMs trained on sufficient
amounts of SQL. The primary reason for the need to generate very long Python
functions is to accommodate different data input types. Nevertheless, we see
improvements from our API functions when applied on top of either query
language in nearly all settings.

##  5 Ablation Studies

We conduct ablation analyses on the HiTab dataset to examine the improvements
brought by assistant API functions (§5.1) and multi-index parsing (§5.2). We
refer to multi-index parsing as w/ MI, and denote the opposing table
flattening approach as w/o MI in the result tables.

API Functions | Multi-Index
---|---
QA | Operation | w/o MI | w/ MI
✗ | ✗ | 59.6 | 56.0
✓ | ✗ | 57.4 | 58.7
✓ | ✓ | 59.1 | 69.4

Table 5: Comparing Codex execution accuracy on HiTab by removing multi-index
parsing or helper API functions. MI stands for Multi-Index parsing. For
experiments without MI, we employ the flattening approach (Figure 7). Figure
7: Representing a structured table by flattening hierarchical headers.

###  5.1 API Functions

We first study the improvement brought by API functions of different types. As
described in §3.3, we provide the model with (i) the QA API, and (ii)
operation APIs. In comparison to the base setting in which neither type of API
is utilized, we add one type of API at a time to examine their gains.

As shown in Table 5, both types of APIs are helpful. Comparing the two API
types, the operation API brings more marginal improvement than that of the QA
API. In particular, adding the QA API increases performance by $2.7\%$, while
further adding the operation APIs improves by another $10.7\%$, compared to
the full system without APIs.

###  5.2 Multi-Index Transformation

Next, we study the contribution of adopting multi-index as a hierarchical
table representation.

In comparison to our multi-index parsing baseline, we experiment with an
alternative table header flattening approach that has been adopted for table
processing in many works (Parikh et al., 2020; Liu et al., 2022; Wang et al.,
2022). More specifically, we flatten the top header hierarchy into a single-
row relational header by concatenating all cell strings from the root to each
leaf header node. Note that this process ignores the header information in
dimensions other than the top and treats them as normal table cells. This
flattened representation is then integrated into our framework using Python
queries, code models, and API calls to facilitate the ablation study. An
illustration of this flattening process is shown in Figure 7.

As shown in Table 5, the execution accuracy decreases by $3.6\%$ with the
multi-index approach compared to the table flattening approach when no API is
included. However, as we involve QA and operation APIs, the multi-index
approach demonstrates a $10.3\%$ improvement over that without multi-indexing.
This indicates that the proposed multi-index representation is essential in
preserving the rich structural information of hierarchical tables, and can be
leveraged by our API operations.

##  6 Related Work

#### QA over Varied Table Structures

Existing methods for table QA face many challenges both within specific table
structures and across table types. SQL queries perform well in solving
questions with relational tables (Pasupat and Liang, 2015; Yu et al., 2018),
but their grammar is often unable to cover the entire spectrum of questions
(Guo et al., 2019). Domain-specific logical forms are often favored when
handling more complicated table structures (Wang et al., 2021a; Katsis et al.,
2022), queries on text (Gupta et al., 2019), and grounded environments such as
visual question answering (Andreas et al., 2016a, b; Johnson et al., 2017).
However, these specifically designed logical forms do not support the
operations needed outside their intended domain (Cheng et al., 2022). In
contrast to previous methods which focus on adapting their solutions to
certain table structures, we transform table structures using the multi-index
format and utilize the natural flexibility within the Python language.
Furthermore, we also introduce the usage of custom API functions as a modular
approach to extend the framework.

#### Program generation and assistant functions

Several works have leveraged program generation to answer questions or carry
out planning tasks (Singh et al., 2022; Liang et al., 2022) within other
environments such those involving visual modalities (Subramanian et al., 2023;
Surís et al., 2023; Gupta and Kembhavi, 2023). Past work has also proposed
connecting natural and programming languages by adding textual QA abilities to
programs (Cheng et al., 2023) or adding programmatic operations to NL (Gao et
al., 2022; Chen et al., 2022). In comparison, we focus more on extending the
limited built-in operations in programming languages (e.g., Python), and
incorporate helper API functions to enable broader capabilities for TableQA
tasks. This is similar to the goal of extending functions into a given
programming language (Herzig et al., 2020; Guo et al., 2019), however, our
APIs also benefit from being easily implemented as Python functions
themselves.

##  7 Conclusion

We introduced a framework for solving general TableQA tasks. This framework is
built upon three core components: a unifying multi-index representation,
Python programs as the query language, and code generation by prompting a
large pretrained code model. Using Codex as the code model, we demonstrate
improvements over the state-of-the-art performance for multiple datasets, each
with its unique table structures and challenges. Through ablations, we show
that our proposed multi-index and API functions are both critical to the
success of the framework, with the largest improvements on datasets involving
hierarchical tables. We also observe improvements in performance for an open-
source model, StarCoder, demonstrating the effectiveness of our approach with
different code models.

## Limitations

We note that though our general framework consistently improves performance
across datasets, we identify through ablations components in our framework
that, individually applied, adversely affect performance on particular
datasets. However, these same components are able to improve performance in
combination with other features of the framework, as well as across other
datasets. Thus, we consider these capabilities to be a step towards solving
general TableQA tasks.

One limitation of our current framework is its manual definition of API
functions, which may not extend to other datasets with disparate table
structures, or involve richer grounded settings. Thus, a future direction for
our work is to automate the API generation for different QA datasets and
questions. We envision an interactive framework that, given feedback on its
performance on a dataset, constructs new API functions to solve question types
with lower performance.

## References

  * Andreas et al. (2016a) Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. 2016a.  Learning to compose neural networks for question answering.  In _NAACL_.
  * Andreas et al. (2016b) Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. 2016b.  Neural module networks.  In _CVPR_ , pages 39–48.
  * Binder et al. (2022) Arne Binder, Leonhard Hennig, and Bhuvanesh Verma. 2022.  Full-text argumentation mining on scientific publications.  In _Proceedings of the first Workshop on Information Extraction from Scientific Publications_ , pages 54–66, Online. Association for Computational Linguistics.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_.
  * Chen et al. (2022) Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. 2022.  Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks.  _arXiv preprint arXiv:2211.12588_.
  * Chen and Cafarella (2013) Zhe Chen and Michael Cafarella. 2013.  Automatic web spreadsheet data extraction.  In _Proceedings of the 3rd International Workshop on Semantic Search over the Web_ , pages 1–8.
  * Cheng et al. (2022) Zhoujun Cheng, Haoyu Dong, Zhiruo Wang, Ran Jia, Jiaqi Guo, Yan Gao, Shi Han, Jian-Guang Lou, and Dongmei Zhang. 2022.  HiTab: A hierarchical table dataset for question answering and natural language generation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1094–1110, Dublin, Ireland. Association for Computational Linguistics.
  * Cheng et al. (2023) Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, Rahul Nadkarni, Yushi Hu, Caiming Xiong, Dragomir Radev, Mari Ostendorf, Luke Zettlemoyer, Noah A. Smith, and Tao Yu. 2023.  Binding language models in symbolic languages.  In _The Eleventh International Conference on Learning Representations_.
  * Gao et al. (2022) Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. 2022.  Pal: Program-aided language models.  _arXiv preprint arXiv:2211.10435_.
  * Glass et al. (2021) Michael Glass, Mustafa Canim, Alfio Gliozzo, Saneem Chemmengath, Vishwajeet Kumar, Rishav Chakravarti, Avi Sil, Feifei Pan, Samarth Bharadwaj, and Nicolas Rodolfo Fauceglia. 2021.  Capturing row and column semantics in transformer based question answering over tables.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1212–1224, Online. Association for Computational Linguistics.
  * Guo et al. (2019) Jiaqi Guo, Zecheng Zhan, Yan Gao, Yan Xiao, Jian-Guang Lou, Ting Liu, and Dongmei Zhang. 2019.  Towards complex text-to-SQL in cross-domain database with intermediate representation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4524–4535, Florence, Italy. Association for Computational Linguistics.
  * Gupta et al. (2019) Nitish Gupta, Kevin Lin, Dan Roth, Sameer Singh, and Matt Gardner. 2019.  Neural module networks for reasoning over text.  _arXiv preprint arXiv:1912.04971_.
  * Gupta and Kembhavi (2023) Tanmay Gupta and Aniruddha Kembhavi. 2023.  Visual programming: Compositional visual reasoning without training.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 14953–14962.
  * Herzig et al. (2020) Jonathan Herzig, Pawel Krzysztof Nowak, Thomas Müller, Francesco Piccinno, and Julian Eisenschlos. 2020.  TaPas: Weakly supervised table parsing via pre-training.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4320–4333, Online. Association for Computational Linguistics.
  * Johnson et al. (2017) Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Judy Hoffman, Li Fei-Fei, C. Lawrence Zitnick, and Ross Girshick. 2017.  Inferring and executing programs for visual reasoning.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_.
  * Katsis et al. (2022) Yannis Katsis, Saneem Chemmengath, Vishwajeet Kumar, Samarth Bharadwaj, Mustafa Canim, Michael Glass, Alfio Gliozzo, Feifei Pan, Jaydeep Sen, Karthik Sankaranarayanan, and Soumen Chakrabarti. 2022.  AIT-QA: Question answering dataset over complex tables in the airline industry.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Industry Track_ , pages 305–314, Hybrid: Seattle, Washington + Online. Association for Computational Linguistics.
  * Li et al. (2023) Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, Qian Liu, Evgenii Zheltonozhskii, Terry Yue Zhuo, Thomas Wang, Olivier Dehaene, Mishig Davaadorj, Joel Lamy-Poirier, João Monteiro, Oleh Shliazhko, Nicolas Gontier, Nicholas Meade, Armel Zebaze, Ming-Ho Yee, Logesh Kumar Umapathi, Jian Zhu, Benjamin Lipkin, Muhtasham Oblokulov, Zhiruo Wang, Rudra Murthy, Jason Stillerman, Siva Sankalp Patel, Dmitry Abulkhanov, Marco Zocca, Manan Dey, Zhihan Zhang, Nour Fahmy, Urvashi Bhattacharyya, Wenhao Yu, Swayam Singh, Sasha Luccioni, Paulo Villegas, Maxim Kunakov, Fedor Zhdanov, Manuel Romero, Tony Lee, Nadav Timor, Jennifer Ding, Claire Schlesinger, Hailey Schoelkopf, Jan Ebert, Tri Dao, Mayank Mishra, Alex Gu, Jennifer Robinson, Carolyn Jane Anderson, Brendan Dolan-Gavitt, Danish Contractor, Siva Reddy, Daniel Fried, Dzmitry Bahdanau, Yacine Jernite, Carlos Muñoz Ferrandis, Sean Hughes, Thomas Wolf, Arjun Guha, Leandro von Werra, and Harm de Vries. 2023.  Starcoder: may the source be with you!
  * Liang et al. (2017) Chen Liang, Jonathan Berant, Quoc Le, Kenneth D. Forbus, and Ni Lao. 2017.  Neural symbolic machines: Learning semantic parsers on Freebase with weak supervision.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 23–33, Vancouver, Canada. Association for Computational Linguistics.
  * Liang et al. (2018) Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoc Le, and Ni Lao. 2018.  Memory augmented policy optimization for program synthesis and semantic parsing.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, page 10015–10027, Red Hook, NY, USA. Curran Associates Inc.
  * Liang et al. (2022) Jacky Liang, Wenlong Huang, Fei Xia, Peng Xu, Karol Hausman, Brian Ichter, Pete Florence, and Andy Zeng. 2022.  Code as policies: Language model programs for embodied control.  _arXiv preprint arXiv:2209.07753_.
  * Liu et al. (2022) Qian Liu, Bei Chen, Jiaqi Guo, Morteza Ziyadi, Zeqi Lin, Weizhu Chen, and Jian-Guang Lou. 2022.  TAPEX: Table pre-training via learning a neural SQL executor.  In _International Conference on Learning Representations_.
  * Nishida et al. (2017) Kyosuke Nishida, Kugatsu Sadamitsu, Ryuichiro Higashinaka, and Yoshihiro Matsuo. 2017.  Understanding the semantic structures of tables with a hybrid deep neural network architecture.  In _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence_ , page 168–174.
  * Parikh et al. (2020) Ankur Parikh, Xuezhi Wang, Sebastian Gehrmann, Manaal Faruqui, Bhuwan Dhingra, Diyi Yang, and Dipanjan Das. 2020.  ToTTo: A controlled table-to-text generation dataset.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1173–1186, Online. Association for Computational Linguistics.
  * Pasupat and Liang (2015) Panupong Pasupat and Percy Liang. 2015.  Compositional semantic parsing on semi-structured tables.  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 1470–1480, Beijing, China. Association for Computational Linguistics.
  * Pourreza and Rafiei (2023) Mohammadreza Pourreza and Davood Rafiei. 2023.  Din-sql: Decomposed in-context learning of text-to-sql with self-correction.  _arXiv preprint arXiv:2304.11015_.
  * Singh et al. (2022) Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. 2022.  Progprompt: Generating situated robot task plans using large language models.  _arXiv preprint arXiv:2209.11302_.
  * Subramanian et al. (2023) Sanjay Subramanian, Medhini Narasimhan, Kushal Khangaonkar, Kevin Yang, Arsha Nagrani, Cordelia Schmid, Andy Zeng, Trevor Darrell, and Dan Klein. 2023.  Modular visual question answering via code generation.
  * Surís et al. (2023) Dídac Surís, Sachit Menon, and Carl Vondrick. 2023.  Vipergpt: Visual inference via python execution for reasoning.  _arXiv preprint arXiv:2303.08128_.
  * Wang et al. (2021a) Fei Wang, Kexuan Sun, Muhao Chen, Jay Pujara, and Pedro Szekely. 2021a.  Retrieving complex tables with multi-granular graph representation learning.  In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’21, page 1472–1482, New York, NY, USA. Association for Computing Machinery.
  * Wang et al. (2015) Yushi Wang, Jonathan Berant, and Percy Liang. 2015.  Building a semantic parser overnight.  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 1332–1342, Beijing, China. Association for Computational Linguistics.
  * Wang et al. (2021b) Zhiruo Wang, Haoyu Dong, Ran Jia, Jia Li, Zhiyi Fu, Shi Han, and Dongmei Zhang. 2021b.  Tuta: Tree-based transformers for generally structured table pre-training.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pages 1780–1790.
  * Wang et al. (2022) Zhiruo Wang, Zhengbao Jiang, Eric Nyberg, and Graham Neubig. 2022.  Table retrieval may not necessitate table-specific model design.  In _Proceedings of the Workshop on Structured and Unstructured Knowledge Integration (SUKI)_ , pages 36–46, Seattle, USA. Association for Computational Linguistics.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. 2018\.  Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQL task.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3911–3921, Brussels, Belgium. Association for Computational Linguistics.
  * Zhu et al. (2021) Fengbin Zhu, Wenqiang Lei, Youcheng Huang, Chao Wang, Shuo Zhang, Jiancheng Lv, Fuli Feng, and Tat-Seng Chua. 2021.  Tat-qa: A question answering benchmark on a hybrid of tabular and textual content in finance.  _arXiv preprint arXiv:2105.07624_.

##  Appendix A Few-shot Results

We further conduct experiments on WikiTableQuestions and HiTab datasets to
study the influence of different shots in the prompt. Results are shown in
Table 6.

Dataset | 5 shots | 12 shots
---|---|---
HiTab | 69.3 | 70.0
WikiTQ | 42.4 | 42.8

Table 6: Execution accuracy on HiTab and WikiTQ with different number of
prompts.

##  Appendix B Prompt Templates

Below we show the templates that we used to prompt code generation models to
give answers.

Figure 8: An prompt example for hierarchical table question answering
problems.

##  Appendix C Incorporating SQL into Python Pandas

The prompt template we use for SQL querying in shown in 9(a) and 9(b). The
generated SQL query is wrapped in
pandasql666https://pypi.org/project/pandasql/ queries and executed using
Python SQLite tools. The return value for these queries is pandas data frames,
upon which our self-designed APIs will take effect. This way of combining SQL
and Python makes it possible to directly apply our Python API functions to
SQL-returned results.

(a) An prompt example for the Spider dataset.

(b) An prompt example for the WikiTQ dataset.

Figure 9:

##  Appendix D Examples for Multi-Index Parsing

See examples of multi-index parsing in both hierarchical table and flat tables
in Figure 10.

(a) A hierarchical table example adapted from HiTab

(b) A multi-table example adapted from Spider

Figure 10: Illustration of multi-index parsing with two datasets. We first
transform the original table(s) into parsed hierarchical tree(s), similar to
HiTab Cheng et al. (2022). Then we parse the hierarchical tree(s) using depth-
first traversal to form the multi-index lists. In 10(a), the top root is
Source and mechanism, whose children define different kinds of source and
mechanism of the participants, while the left root is All full-time, whose
children consist of different kinds of full-time jobs. With the final output
of the multi-index representation, all cells can be uniquely identified, and
thus can reconstruct the table using a simple Pandas code. We also present an
example of flat tables in 10(b), demonstrating the general applicability of
our method.  Figure 11:  The table is the distribution of new immigrants in
different regions/provinces of Canada adapted from HiTab. One question related
to this table is “how much percentage point has Manitoba rose when it comes to
immigrants intended landing destination”. However, the information that
Winnipeg is a city of Manitoba is not included in the table itself. In such
case, no method we tested could give the correct answer, which should contain
a numerator that adds up "Winnipeg" and "Rest of Manitoba". In contrast, by
calling QA API qa("Manitoba?", left root, 1) to Codex, which returns an answer
yes to both "Winnipeg" and "Rest of Manitoba", code models could return the
accurate answer to this question.


# Moore machines duality

Jacques Peyrière  Renmin University of China, School of Mathematics, 100872
Beijing, P.R. China, and Institut de Mathématiques d’Orsay, CNRS, Université
Paris-Saclay, 91405 Orsay, France.  jacques.peyriere@umiversite-paris-
saclay.fr

(Date: June 22, 2020)

###### Abstract.

We present a simple algorithm to find the Moore machine with the minimun
number of states equivalent to a given one.

###### Key words and phrases:

finite automaton, Moore machine, morphism of free monoid

###### 1991 Mathematics Subject Classification:

2020 classification: 68Q45, 68Q70, 03D05

##  1\. Introduction

It is known that there is a unique, up to isomorphism, deterministic finite
automaton with a minimum number of states which recognizes the same language
as a given one. As explained in [7] (pages 29–30), the states of this minimal
automaton can be taken as the classes modulo an equivalence relation on the
input words.

Several algorithms to minimize a deterministic finite automaton has been
proposed [4, 5, 8]. According to [2] these algorithms fall within three
categories. Some of them apply as well to non deterministic finite automata
and to Moore machines.

In Section 2.5 we describe an algorithm to minimize a Moore machine, and
establish its consistency. This algorithm lies in the same family as
Brzozowski’s one [5]. But its description as well as the proof of its
correctness are very simple and do not require much apparatus. Furthermore,
this gives another proof, simple and elementary, of the existence and
uniqueness of a minimum automaton (see Section 3). In Section 4 we extend
these results to morphisms of free monoids.

##  2\. Moore machine and duality

######  Definition 1.

A Moore machine is a 6-tuple
$\mathscr{M}=(Q,\Sigma,\Delta,\delta,{\lambda},{\mathsf{i}})$ where

  * –

$Q$ is a finite set, the set of states,

  * –

$\Sigma$ is a finite set, the input alphabet,

  * –

$\Delta$ is a finite set, the output alphabet,

  * –

$\delta$ is a mapping from $Q\times\Sigma$ to $Q$, called the transition
function,

  * –

${\lambda}\in\Delta^{Q}$ is a mapping from $Q$ to $\Delta$,

  * –

${\mathsf{i}}\in Q$ is the initial state.

###  2.1. Actions of words on $Q$

The set of words on the alphabet $\Sigma$, including the empty word
$\epsilon$, is denoted by $\Sigma^{*}$. The concatenation of the words $u$ and
$v$ is simply written $uv$.

The transition function $\delta$ can be extended in two ways as a mapping from
$Q\times\Sigma^{*}$ to $Q$.

  * Right action. We define, by recursion on the length of $w$ a mapping, written $(a,w)\mapsto a\\!\cdot\\!w$, from $Q\times\Sigma^{*}$ to $Q$:

    * –

for $a\in Q$, $a\\!\cdot\\!\epsilon=a$,

    * –

for $a\in Q$ and $j\in\Sigma$, $a\\!\cdot\\!j=\delta(a,j)$,

    * –

$a\\!\cdot\\!wj=(a\\!\cdot\\!w)\\!\cdot\\!j$ for $a\in Q,\ w\in\Sigma^{*}$,
and $j\in\Sigma$.

  * Left action. In the same way we define a mapping, written $(w,a)\mapsto w\\!\cdot\\!a$, from $\Sigma^{*}\times Q$ to $Q$:

    * –

for $a\in Q$, $\epsilon\\!\cdot\\!a=a$,

    * –

for $a\in Q$ and $j\in\Sigma$, $j\\!\cdot\\!a=\delta(a,j)$,

    * –

$jw\\!\cdot\\!a=j\\!\cdot\\!(w\\!\cdot\\!a)$ for $a\in Q,\ w\in\Sigma^{*}$,
and $j\in\Sigma$.

###  2.2. Right and left machines

We can feed ${\mathscr{M}}$ with a word in $\Sigma^{*}$ on the right or on the
left and get an output:

${\mathscr{M}}\\!\cdot\\!w={\lambda}({\mathsf{i}}\\!\cdot\\!w)\text{\quad and
\quad}w\\!\cdot\\!{\mathscr{M}}={\lambda}(w\\!\cdot\\!{\mathsf{i}}).$

If a state does not belong to the set $\\{{\mathsf{i}}\\!\cdot\\!w\ :\
w\in\Sigma^{*}\\}$, it is useless and can be removed. From now on we assume
that $G=\\{{\mathsf{i}}\\!\cdot\\!w\ :\ w\in\Sigma^{*}\\}$.

Of course, since
$w\\!\cdot\\!{\mathscr{M}}={\mathscr{M}}\\!\cdot\\!\overline{w}$ (where
$\overline{w}$ stands for the mirror word of $w$) it would be enough to
consider right actions only. But using both actions will prove convenient in
what follows.

We say that two Moore machines ${\mathscr{M}}$ and ${\mathscr{M}}^{\prime}$,
with the same $\Sigma$ and $\Delta$, are equivalent if, for all
$w\in\Sigma^{*}$,
${\mathscr{M}}\\!\cdot\\!w={\mathscr{M}}^{\prime}\\!\cdot\\!w$.

Let ${\mathscr{M}}$ and ${\mathscr{M}}^{\prime}$ be two Moore machines. If
there exists a bijection $\xi$ from $Q$ onto $Q^{\prime}$ such that, for all
$a\in Q$ and $j\in\Sigma$, $\delta^{\prime}(\xi(a),j)=\xi(\delta(a),j)$ and
${\lambda}^{\prime}\bigl{(}\xi(a)\bigr{)}={\lambda}(a)$, we say that these two
machines are isomorphic.

###  2.3. Duals

#### Actions of words on functions

If $f$ is a function from $Q$ to some set and $w\in\Sigma^{*}$ we define two
functions $w\\!\cdot\\!f$ and $f\\!\cdot\\!w$:

$\text{for all\quad}a\in Q,\quad(w\\!\cdot\\!f)(a)=f(a\\!\cdot\\!w)\text{\quad
and\quad}(f\\!\cdot\\!w)(a)=f(w\\!\cdot\\!a)$

Then
$\bigl{(}(vw)\\!\cdot\\!f\bigr{)}(a)=f\bigl{(}a\\!\cdot\\!(vw)\bigr{)}=(w\\!\cdot\\!f)(a\\!\cdot\\!v)=\bigl{(}v\\!\cdot\\!(w\\!\cdot\\!f)\bigr{)}(a)$.
So,

$(vw)\\!\cdot\\!f=v\\!\cdot\\!(w\\!\cdot\\!f)$

and similarly

$f\\!\cdot\\!(vw)=(f\\!\cdot\\!v)\\!\cdot\\!w$

#### Right dual

This is the Moore machine
${\mathscr{M}}_{\star}=(Q_{\star},\Sigma,\Delta,\delta_{\star},{\lambda}_{\star},{\mathsf{i}}_{\star})$
defined as follows:
$Q_{\star}=\\{w\\!\cdot\\!\lambda\ :\ w\in\Sigma^{*}\\}\subset\Delta^{Q}$
$\delta_{\star}(f,j)=j\\!\cdot\\!f$
${\lambda}_{\star}\ :\ Q_{\star}\longrightarrow\Delta$ so defined:
${\lambda}_{\star}(f)=f({\mathsf{i}})$
${\mathsf{i}}_{\star}={\lambda}$.

Then, for all $w\in\Sigma^{*}$,
${\lambda}_{\star}(w\\!\cdot\\!{\mathsf{i}}_{\star})=(w\\!\cdot\\!{\mathsf{i}}_{\star})({\mathsf{i}})=(w\\!\cdot\\!{\lambda})({\mathsf{i}})={\lambda}({\mathsf{i}}\\!\cdot\\!w)$,
which means

$w\\!\cdot\\!{\mathscr{M}}_{\star}={\mathscr{M}}\\!\cdot\\!w$

#### Left dual

We define the machine
$\vphantom{\mathscr{M}}{}_{\star}\mathscr{M}=(\vphantom{Q}_{\star}Q,\Sigma,\Delta,\vphantom{\delta}_{\star}\delta,\vphantom{{\lambda}}_{\star}{\lambda},\vphantom{{\mathsf{i}}}_{\star}{\mathsf{i}})$
in the same way:
$\vphantom{Q}{}_{\star}Q=\\{{\lambda}\\!\cdot\\!w\ :\
w\in\Sigma^{*}\\}\subset\Delta^{Q}$
$\vphantom{\delta}{}_{\star}\delta(f,j)=f\\!\cdot\\!j$
$\vphantom{{\lambda}}{}_{\star}{\lambda}\ :\ Q_{\star}\longrightarrow\Delta$
so defined: ${\lambda}_{\star}(f)=f({\mathsf{i}})$,
$\vphantom{{\mathsf{i}}}{}_{\star}{\mathsf{i}}={\lambda}$.

Then, for all $w\in\Sigma^{*}$,
$\vphantom{{\lambda}}{}_{\star}{\lambda}(\vphantom{{\mathsf{i}}}_{\star}{\mathsf{i}}\\!\cdot\\!w)=(\vphantom{{\mathsf{i}}}_{\star}{\mathsf{i}}\\!\cdot\\!w)({\mathsf{i}})=({\lambda}\\!\cdot\\!w)({\mathsf{i}})={\lambda}(w\\!\cdot\\!{\mathsf{i}})$,
which means

$\vphantom{\mathscr{M}}{}_{\star}\mathscr{M}\\!\cdot\\!w=w\\!\cdot\\!{\mathscr{M}}$

###  2.4. Bidual

To avoid cumbersome notation, set
${\mathscr{M}}^{\natural}=\vphantom{({\mathscr{M}}_{\star})}_{\star}({\mathscr{M}}_{\star})$.
Then both $\mathscr{M}$ and ${\mathscr{M}}^{\natural}$ are right machines and
are equivalent in that sense that they give the same outputs.

There is a natural mapping $\tau$ from $Q$ into $\Delta^{Q_{\star}}$:
let $a\in Q$ and $f\in Q_{\star}$, then $f\in\Delta^{Q}$, so $f(a)\in\Delta$;
set $\tau_{a}(f)=f(a)$. Then $\tau\,:\,a\mapsto\tau_{a}$ is a mapping from $Q$
to $\Delta^{Q_{\star}}$.

We have
$({\lambda}_{\star}\\!\cdot\\!w)(f)={\lambda}_{\star}(w\\!\cdot\\!f)=(w\\!\cdot\\!f)({\mathsf{i}})=f({\mathsf{i}}\\!\cdot\\!w)=\tau_{{\mathsf{i}}\cdot
w}(f)$
for all $w\in\Sigma^{*}$ and $f\in Q_{\star}$. So

${\lambda}_{\star}\\!\cdot\\!w=\tau_{{\mathsf{i}}\cdot w}\text{\quad for
all\quad}w\in\Sigma^{*}.$

Since $Q^{\natural}=\\{\lambda_{\star}\\!\cdot\\!w\ :\
w\in\Sigma^{*}\\}\subset\Delta^{Q_{\star}}$, then $\tau$ maps $Q$ onto
${Q}^{\natural}$, and
$\operatorname{{\mathrm{c}ard}}{Q}^{\natural}\leq\operatorname{{\mathrm{c}ard}}Q$.

One would like to know when
$\operatorname{{\mathrm{c}ard}}{Q}^{\natural}=\operatorname{{\mathrm{c}ard}}Q$,
that is when $\tau$ is one-to-one. Let $a\in Q$ and $b\in Q$. Then

$\displaystyle\tau_{a}=\tau_{b}$ $\displaystyle\Longleftrightarrow$
$\displaystyle\forall f\in Q_{\star},f(a)=f(b)$
$\displaystyle\Longleftrightarrow$ $\displaystyle\forall
w\in\Sigma^{*},(w\\!\cdot\\!\lambda)(a)=(w\\!\cdot\\!\lambda)(b)$
$\displaystyle\Longleftrightarrow$ $\displaystyle\forall
w\in\Sigma^{*},{\lambda}(a\\!\cdot\\!w)={\lambda}(b\\!\cdot\\!w).$

Also, one can consider the mapping $\tau_{\star}$ from $Q_{\star}$ to
$\Delta^{{Q}^{\natural}}$ defined in the same way as $\tau$ is:

$\tau_{\star,a}(f)=f(a)\text{\quad for \quad}a\in Q\\_\star\text{ and }f\in
Q^{\natural}.$

Let $a_{\star}\in Q_{\star}$ and $b_{\star}\in Q_{\star}$. Then

$\displaystyle\tau_{\star,a_{\star}}=\tau_{\star,b_{\star}}$
$\displaystyle\Longleftrightarrow$ $\displaystyle\forall f\in
Q^{\natural},f(a_{\star})=f(b_{\star})$ $\displaystyle\Longleftrightarrow$
$\displaystyle\forall
w\in\Sigma^{*},(\lambda_{\star}\\!\cdot\\!w)(a_{\star})=(\lambda_{\star}\\!\cdot\\!w)(b_{\star})$
$\displaystyle\Longleftrightarrow$ $\displaystyle\forall
w\in\Sigma^{*},\lambda_{\star}(w\\!\cdot\\!a_{\star})=\lambda_{\star}(w\\!\cdot\\!b_{\star})$
$\displaystyle\Longleftrightarrow$ $\displaystyle\forall
w\in\Sigma^{*},(w\\!\cdot\\!a_{\star})({\mathsf{i}})=(w\\!\cdot\\!b_{\star})({\mathsf{i}})$
$\displaystyle\Longleftrightarrow$ $\displaystyle\forall
w\in\Sigma^{*},a_{\star}({\mathsf{i}}\\!\cdot\\!w)=b_{\star}({\mathsf{i}}\\!\cdot\\!w)$
$\displaystyle\Longleftrightarrow$ $\displaystyle\forall a\in
Q,a_{\star}(a)=b_{\star}(a)$ $\displaystyle\Longleftrightarrow$ $\displaystyle
a_{\star}=b_{\star}.$

This means that $\tau_{\star}$ is one-to-one and that ${\mathscr{M}}_{\star}$
is equal to its bidual. In the same way
$\vphantom{\mathscr{M}}{}_{\star}\mathscr{M}$ is equal to its bidual.
Therefore ${\mathscr{M}}^{\natural}$ is equal to its bidual.

###  2.5. The algorithm

We illustrate these constructions with the following example.

$\begin{array}[t]{c||c|c}\lx@intercol\hfil\text{Transition}\hfil\lx@intercol\\\
\hline\cr&0&1\\\ \hline\cr{\mathsf{i}}&{\mathsf{i}}&a\\\ a&b&{\mathsf{i}}\\\
b&b&a\end{array}\quad\begin{array}[t]{c|c}\lx@intercol\hfil\lambda\hfil\lx@intercol\\\
\hline\cr{\mathsf{i}}&0\\\ a&1\\\ b&0\end{array}$

Here $Q=\\{{\mathsf{i}},a,b\\}$, $\Sigma=\\{0,1\\}$, and $\Delta=\\{0,1\\}$.
The transition and the output function are defined by the above tables. Also,
as it is customary, this machine is described by the above diagram.

Now we describe an algorithm on this example. We consider a stack whose
members are elements of $\Delta^{Q}$. We start with the stack whose $\lambda$
is the only element.We say that an element $\alpha$ of the stack is happy if
$0\\!\cdot\\!\alpha$ and $1\\!\cdot\\!\alpha$ are both elements of the stack.
To add elements to the stack proceed as follows: starting from the bottom take
the first unhappy element, say $\alpha$, put $0\\!\cdot\\!\alpha$ on the top,
set $\delta_{\star}(\alpha,0)=0\\!\cdot\\!\alpha$, and do the same with
$1\\!\cdot\\!\alpha$.Repeat until all the elements are happy. Then $Q_{\star}$
is the set of elements of the stack and the transition function is
$\delta_{\star}$.

The following table is the result of this process. A column whose first
element is $w\\!\cdot\\!\lambda$ contains two sub-columns; the left one
contains the states ${\mathsf{i}}\\!\cdot\\!w,\,a\\!\cdot\\!w$, and
$b\\!\cdot\\!w$, the right one contains $w\\!\cdot\\!\lambda$, i.e.,
$\lambda({\mathsf{i}}\\!\cdot\\!w),\,\lambda(a\\!\cdot\\!w)$, and
$\lambda(b\\!\cdot\\!w)$. The last line is just a renaming of the states. This
is illustrated by the diagram and the tables below.

$\begin{array}[]{lr|lr|lr|lr|lr|lr|lr|lr|lr}\lx@intercol\hfil\lambda\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
0\\!\cdot\\!\lambda\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
1\\!\cdot\\!\lambda\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
00\\!\cdot\\!\lambda\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
10\\!\cdot\\!\lambda\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
01\\!\cdot\\!\lambda\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
11\\!\cdot\\!\lambda\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
001\\!\cdot\\!\lambda\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
101\\!\cdot\\!\lambda\hfil\lx@intercol\\\
\hline\cr\hline\cr{\mathsf{i}}&0&{\mathsf{i}}&0&a&1&{\mathsf{i}}&0&b&0&a&1&{\mathsf{i}}&0&a&1&a&1\\\
\hline\cr a&1&b&0&{\mathsf{i}}&0&b&0&{\mathsf{i}}&0&a&1&a&1&a&1&a&1\\\
\hline\cr b&0&b&0&a&1&b&0&b&0&a&1&{\mathsf{i}}&0&a&1&a&1\\\
\hline\cr\hline\cr\lx@intercol\hfil t\hfil\lx@intercol&\lx@intercol\hfil
u\hfil\lx@intercol&\lx@intercol\hfil v\hfil\lx@intercol&\lx@intercol\hfil
u\hfil\lx@intercol&\lx@intercol\hfil u\hfil\lx@intercol&\lx@intercol\hfil
w\hfil\lx@intercol&\lx@intercol\hfil t\hfil\lx@intercol&\lx@intercol\hfil
w\hfil\lx@intercol&\lx@intercol\hfil w\hfil\lx@intercol\end{array}$

$\begin{array}[b]{c||c|c}\lx@intercol\hfil\text{Transition}\hfil\lx@intercol\\\
\hline\cr&0&1\\\ \hline\cr t&u&v\\\ u&u&u\\\ v&w&t\\\
w&w&w\end{array}\quad\begin{array}[b]{c|c}\lx@intercol\hfil\lambda_{\star}\hfil\lx@intercol\\\
\hline\cr t&0\\\ u&0\\\ v&1\\\ w&1\end{array}$

The following is the computation of the bidual (the states $u$ and $w$ have
been omitted in the next table because they would not have brought any
information).

$\begin{array}[]{|lr|lr|lr|lr|lr|}\lx@intercol\hfil\lambda_{\star}\hfil\lx@intercol&\lx@intercol\hfil\lambda_{\star}\\!\cdot\\!0\hfil\lx@intercol&\lx@intercol\hfil\lambda_{\star}\\!\cdot\\!1\hfil\lx@intercol&\lx@intercol\hfil\lambda_{\star}\\!\cdot\\!10\hfil\lx@intercol&\lx@intercol\hfil\lambda_{\star}\\!\cdot\\!11\hfil\lx@intercol\\\
\hline\cr\hline\cr t&0&u&0&v&1&u&0&t&0\\\ \hline\cr v&1&w&1&t&0&w&1&v&1\\\
\hline\cr\hline\cr\lx@intercol\hfil x\hfil\lx@intercol&\lx@intercol\hfil
x\hfil\lx@intercol&\lx@intercol\hfil y\hfil\lx@intercol&\lx@intercol\hfil
x\hfil\lx@intercol&\lx@intercol\hfil x\hfil\lx@intercol\end{array}$

$\begin{array}[b]{c||c|c}\lx@intercol\hfil\text{Transition}\hfil\lx@intercol\\\
\hline\cr&0&1\\\ \hline\cr x&x&y\\\
y&x&x\end{array}\quad\begin{array}[b]{c|c}\lx@intercol\hfil{\lambda}^{\natural}\hfil\lx@intercol\\\
\hline\cr x&0\\\ y&1\end{array}$

As expected, the bidual has less states as the original machine.

##  3\. Minimal Moore machine

Here we give another proof of the existence and uniqueness of the minimal
machine.

###  3.1. Product of machines

Let
${\mathscr{M}}_{1}=(Q_{1},\Sigma,\Delta_{1},\delta_{1},\lambda_{1},{\mathsf{i}}_{1})$
and
${\mathscr{M}}_{2}=(Q_{2},\Sigma,\Delta_{2},\delta_{2},\lambda_{2},{\mathsf{i}}_{2})$
be two Moore machines, $\Delta$ a finite set, and $\gamma$ a mapping from
$\Delta_{1}\times\Delta_{2}$ to $\Delta$. We define a new machine

${\mathscr{M}}_{1}\otimes_{\gamma}{\mathscr{M}}_{2}=\bigl{(}Q,\Sigma,\Delta,\delta,\gamma\circ(\lambda_{1}\times\lambda_{2}),({\mathsf{i}}_{1},{\mathsf{i}}_{2})\bigr{)}$

by setting

$Q=\\{({\mathsf{i}}_{1}\\!\cdot\\!w,{\mathsf{i}}_{2}\\!\cdot\\!w)\
:w\in\Sigma^{*}\\}\text{ and
}\delta\bigl{(}(a_{1},a_{2}),j\bigr{)}=\bigl{(}\delta_{1}(a_{1},j),\delta_{2}(a_{2},j)\bigr{)}.$

###  3.2. Minimal Moore machine

Let ${\mathscr{M}}_{1}$ and ${\mathscr{M}}_{2}$ be two equivalent right
machines such that each one is isomorphic to its bidual.

Let $p_{1}$ and $p_{2}$ be the projections of $Q_{1}\times Q_{2}$ onto $Q_{1}$
and $Q_{2}$. Consider the machines
${\mathscr{B}}_{k}={\mathscr{M}_{1}}\otimes_{p_{k}}{\mathscr{M}}_{2}$, for
$k=1,2$.

For $w\in\sigma^{*}$, $k\in\\{1,2\\}$, and $(a_{1},a_{2})\in Q_{1}\times
Q_{2}$ we have

$\displaystyle\Bigl{(}w\\!\cdot\\!\bigl{(}p_{k}\circ(\lambda_{1}\times\lambda_{2})\bigr{)}\Bigg{)}(a_{1},a_{2})$
$\displaystyle=$ $\displaystyle
p_{k}\circ(\lambda_{1}\times\lambda_{2})(a_{1}\\!\cdot\\!w,a_{2}\\!\cdot\\!w)$
$\displaystyle=$
$\displaystyle\lambda_{k}(a_{k}\\!\cdot\\!w)=(w\\!\cdot\\!\lambda_{k})(a_{k}).$

This means
$w\\!\cdot\\!\bigl{(}p_{k}\circ(\lambda_{1}\times\lambda_{2})\bigr{)}=(w\\!\cdot\\!\lambda_{y})\circ
p_{k}$, which implies ${\mathscr{B}}_{k\star}={\mathscr{M}}_{k\star}$.
Therefore
${\mathscr{B}}_{k}^{\natural}={\mathscr{M}}_{k}^{\natural}={\mathscr{M}}_{k}$

Because ${\mathscr{M}}_{1}$ and ${\mathscr{M}}_{2}$ are equivalent we have
$\lambda_{1}(a_{1})=\lambda_{2}(a_{2})$ for all $(a_{1},a_{2})\in Q$ (i.e.,
$a_{1}={\mathsf{i}}_{1}\\!\cdot\\!w$ and $a_{2}={\mathsf{i}}_{2}\\!\cdot\\!w$
for some $w\in\Sigma^{*}$). Therefore ${\mathscr{B}}_{1}={\mathscr{B}}_{2}$.

As a conclusion, for any Moore machine, there is a unique (up to isomorphism)
simplest equivalent machine which is the bidual. One could notice that this
algorithm provides a normal form for a Moore machine.

##  4\. Substitutions

Consider a 5-tuple ${\mathscr{S}}=(Q,\Delta,\sigma,\lambda,{\mathsf{i}})$
where

  * –

$Q$ and $\Delta$ are finite sets,

  * –

$\sigma$ is an endomorphism of the free monoid $Q^{*}$ generated by $Q$,

  * –

$\lambda$ is a mapping from $Q$ to $\Delta$,

  * –

${\mathsf{i}}\in Q$.

The endomorphism $\sigma$, also called substitution, is determined by the
images of the generators, i.e., by the words $\\{\sigma(a)\\}_{a\in Q}$. We
adopt the following notation: if $w$ is a word on some alphabet, $|w|$ stands
for its length (i.e., the number of letters it is made of), and $w_{j}$ stands
for its $(j+1)$-th letter from the left (the letters are numbered 0, 1, 2, …).
Let $q=\displaystyle\max_{a\in Q}|\sigma(a)|$.

When $\delta({\mathsf{i}},0)={\mathsf{i}}$, the words
$\bigl{(}\sigma^{n}({\mathsf{i}})\bigr{)}_{n\geq 0}$ have a limit
$\sigma^{\infty}({\mathsf{i}})$ in $Q^{\mathbb{N}}$. Such sequences as
$\lambda\bigl{(}\sigma^{\infty}({\mathsf{i}})\bigr{)}$, called projections of
fixed points of substitutions, have been studied in many contexts, namely for
their algebraic, dynamic, and combinatoric properties [1, 6, 3].

### Constant length substitutions

This is the cas when $|\sigma(a)|=q$ for all $a\in Q$. We then set
$\Sigma=\\{0,1,\dots,q-1\\}$ and $\delta(a,j)=\sigma(a)_{j}$ for $a\in Q$ and
$0\leq j<q$. So we have a Moore machine:

${\mathscr{M}}=(Q,\Sigma,\Delta,\delta,\lambda,{\mathsf{i}}).$

In this context if $k\geq 0$ and $n=n_{0}+n_{1}q+\dots n_{k-1}q^{k-1}$ (the
base $q$ expansion of $n$) it is easy to see that the letter of index $n$ in
the word $\sigma^{k}(a)$ is $n_{0}n_{1}\dots n_{k-1}\\!\cdot\\!a$, i.e.,

(1) $\bigl{(}\sigma^{k}(a)\bigr{)}_{n}=n_{0}n_{1}\dots n_{k-1}\\!\cdot\\!a.$

This is the connection between Moore machines and substitutions. The bidual of
the left Moore machine $\mathscr{M}$ defines a substitution on a smaller
alphabet equivalent to the original one.

### Non constant length substitutions

Let $\omega$ be a symbol not in $Q$. Set $Q^{\prime}=Q\cup\\{\omega\\}$ and
$\Sigma=\\{0,1,\dots,q-1\\}$. For $0\leq j<q$ set $\delta(\omega,j)=\omega$,
and for $a\in Q$ set $\delta(a,j)=\bigl{(}\sigma(a)\omega^{\nu}\bigr{)}_{j}$,
where $\nu=q-|\sigma(a)|$.

We just have defined a finite automaton
$\mathscr{A}=(Q^{\prime},\Sigma,\delta,{\mathsf{i}},Q)$, where ${\mathsf{i}}$
is the initial state and $Q$ is the set of final states. Let $\mathscr{L}$ be
the language recognized by $\mathscr{A}$ considered as a left automaton :
${\mathscr{L}}=\\{w\in\Sigma^{*}\ :\ w\\!\cdot\\!{\mathsf{i}}\neq\omega\\}$.
If we define $\lambda(\omega)$ arbitrarily, we also have a Moore machine,
${\mathscr{M}}=(Q^{\prime},\Sigma,\Delta,\delta,\lambda,{\mathsf{i}})$. Let
${\mathscr{L}}^{\prime}={\mathscr{L}}\setminus\\{\epsilon\\}$. Observe that,
if $w\in{\mathscr{L}}^{\prime}$, the path leading to
$w\\!\cdot\\!{\mathsf{i}}$ does not include any $\omega$.

If $w\in{\mathscr{L}}^{\prime}$, set $\varphi(w)=\displaystyle\sum_{0\leq
j<|w|}w_{j}q^{j}$. Then the order on $\mathbb{N}$ induces a well-order on
${\mathscr{L}}^{\prime}$: $v\prec w\Leftrightarrow\varphi(v)<\varphi(w)$. So,
we can define $\psi(n)$ to be the $n$-th element of ${\mathscr{L}}^{\prime}$
(starting from $0$). Then the counterpart of (1) is

$\bigl{(}\sigma^{k}({\mathsf{i}})\bigr{)}_{j}=\psi(j)\\!\cdot\\!{\mathsf{i}}$

for $k\geq 0$ and $0\leq j<|\sigma^{k}({\mathsf{i}})|$.

As previously, the bidual of the left Moore machine $\mathscr{M}$ defines a
substitution on a smaller alphabet equivalent to the original one.

Nevertheless, observe that instead of appending some $\omega$’s one could have
padded the $\sigma(a)$’s up to size $q$ by inserting $\omega$’s in various
places. Then, of course, the language $\mathscr{L}$ would be different, but
the above analysis still holds.

## References

  * [1] Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press 2003.
  * [2] Jean Berstel, Luc Boasson, Olivier Carton, and Isabelle Fagnot,  Minimization of Automata, in Automata: from Mathematics to Applications, European Mathematical Society (2010) (arXiv 1010.5318)
  * [3] Valérie Berthé, Sébastien Ferenczi, Christian Mauduit, and Anne Siegel Eds., Substitutions in Dynamics, Arithmetics and Combinatorics. Lecture Notes in Mathematics 1794. Springer 2002, 321–342. ISSN 0075-8434, ISBN 3-540-44141-7.
  * [4] Filippo Bonchi, Marcello M. Bonsangue, Jan J.M.M. Rutten, and Alexandra Silva, R.L. Constable and A. Silva (Eds.): Kozen Festschrift, LNCS 7230, 12–-23. Springer-Verlag Berlin Heidelberg 2012
  * [5] Brzozowski, J. A. (1963), Canonical regular expressions and minimal state graphs for definite events, Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., 529–561, MR 0175719.
  * [6] Gilles Christol, Teturo Kamae, Michel Mendès France, Gérard Rauzy,  Suites algébriques, automates et substitutions, Bull. Soc. Math. France 108 (1980), 401–419.
  * [7] John E. Hopcroft and Jeffrey D, Ullman, Formal Languages and their Applications to Automata, Addison Wesley, 1969\.
  * [8] Moore E. F.,  Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies 34, 129–153. Princeton University Press, Princeton, N.J.(1956).