# D-Graph: AI-Assisted Design Concept Exploration Graph

Shin Sano<EMAIL_ADDRESS>0002-1050-5008 and  Seiji Yamada<EMAIL_ADDRESS>Graduate University for Advanced Studies, SOKENDAI2 Chome-1-2
HitotsubashiChiyodaTokyoJapan101-8430

###### Abstract.

We present an AI-assisted search tool, the “Design Concept Exploration Graph”
(“D-Graph”). It assists automotive designers in creating an original design-
concept phrase, that is, a combination of two adjectives that conveys product
aesthetics. D-Graph retrieves adjectives from a ConceptNet knowledge graph as
nodes and visualizes them in a dynamically scalable 3D graph as users explore
words. The retrieval algorithm helps in finding unique words by ruling out
overused words on the basis of word frequency from a large text corpus and
words that are too similar between the two in a combination using the cosine
similarity from ConceptNet Numberbatch word embeddings. Our experiment with
participants in the automotive design field that used both the proposed
D-Graph and a baseline tool for design-concept-phrase creation tasks suggested
a positive difference in participants’ self-evaluation on the phrases they
created, though not significant. Experts’ evaluations on the phrases did not
show significant differences. Negative correlations between the cosine
similarity of the two words in a design-concept phrase and the experts’
evaluation were significant. Our qualitative analysis suggested the directions
for further development of the tool that should help users in adhering to the
strategy of creating compound phrases supported by computational linguistic
principles.

intelligent interactive system, concept design, knowledge graph

††conference: Helsinki, Finland ’22: The 27th ACM Conference on Intelligent
User Interfaces; March 22–25, 2022; Helsinki, Finland††booktitle: Helsinki,
Finland ’22: ACM Conference on Intelligent User Interfaces, March 22–25, 2022,
Helsinki, Finland††isbn: 978-1-4503-XXXX-X/18/06††ccs: Human-centered
computing Interactive systems and tools††ccs: Information systems Specialized
information retrieval††ccs: Applied computing Arts and humanities††ccs:
Computing methodologies Lexical semantics

##  1\. Introduction

Our goal is to develop and evaluate an intelligent UI that helps automotive
concept designers to verbalize a original design concept with a phrase that
expresses the aesthetics, mood, and emotional quality of a product. The
contributions of this research are as follows. 1. We implement compound
phrases using an adjective-adjective formula. 2. We implement algorithms that
support users in creating a unique adjective-adjective phrase and terms that
contrast with it to help create a character space.

###  1.1. Aesthetic quality of design and its verbal representations

The design in this study is primarily concerned with creating product
aesthetics, defined as the characteristics that make up a product’s
appearance, including materials, proportion, color, ornamentation, shape,
size, and reflectivity (Lawson, 2006). In this section, we will discuss the
relationship between product aesthetics and their verbal representations.
Designers are in charge of creating the meanings and character attached to
their designs and communicating them with other stakeholders in both visual
and verbal modes (Chiu and Shu, 2012a; Koch et al., 2019; Kita and Rekimoto,
2018). In the practices used in automotive design, designers exchange views on
the form of a vehicle design as part of the design process. This requires them
to communicate different shapes and features in words, such as “slippery,”
“exciting,” “fluid,” “tailored,” and “sheer.” Such language used in car design
studios describes particular forms or connotes a “feeling.” This language
often tends to be “idiosyncratic and atypical” (Tovey, 1992). Bouchard et al.
(Bouchard et al., 2005) described these verbal expressions as “intermediate
representations (IR)” and apparent especially in car design cases.

###  1.2. Design concept phrase and character space

We define a design concept phrase (“DCP”) as a combination of two adjectives
that conveys product aesthetics. For example, “kinetic warmth” was created by
the designers at Toyota’s North American design studio for Concept-i [50](Fig.
2-b). Note that the adjective “warm” was converted to a noun form. This
unusually sounding DCP was iterated and communicated using the “character
space,” which consists of two orthogonally crossed semantic differentials. A
character space explains the design concepts in terms of how and by which
attributes they differ and what already exists or what is to be avoided
(Krippendorff, 2005). As illustrated by Tovey as “idiosyncratic and atypical,”
a DCP should be non-cliché and use peculiar language to the extent that it
calls for a design team to invent unique product aesthetics. While Han et al.
(Han et al., 2021) found that aesthetics have a positive relationship with the
creativity of designs, there’s little computational support for verbally
conceptualizing product aesthetics. To fill this gap, we present an AI-
assisted search tool, the “Design Concept Exploration Graph” (“D-Graph”),
which assists automotive designers in creating a novel design-concept phrase.

Figure 1. (a) left:The Character space for “kinetic qarmth” (b) right: the
design derived from “kinetic warmth”(© 2021 Toyota Motor Sales, U.S.A., Inc.).

##  2\. Related Work

###  2.1. Computational mind-mapping tools

While our D-Graph uses a visualized knowledge graph, other computational mind-
mapping tools may seemingly look similar. Spinneret(Bae et al., 2020) uses the
ConceptNet knowledge graph and provides idea suggestions as nodes on the
graph. It uses random walks with breadth-first and depth-first search biases
to explore ideas and provides “suggestions” for the user to add to a mind map.
Its goal is to support divergent thinking, so the algorithm attempts to pursue
depth for concepts in the graph and to overcome the “design fixation” (Jansson
and Smith, 1991) problem. Mini-Map (Chen et al., 2019) also uses ConceptNet,
and it gamifies the process of mind-mapping, where a user collaboratively
creates a mind map with an intelligent agent. The authors measured the
diversification of ideas in a graph by using dimensionality reduction for the
semantic distance between the ideas in mind-maps. Our approach is different as
our goal is to assist users in examining the nuances of words within a
particular semantic space, and the distance is only incorporated between the
two words in the DCP.

###  2.2. Combinational creativity

Combinational creativity produces new ideas by combining existing ideas in
unfamiliar ways (Boden, 2001). A number of studies have identified the effect
of language as a tool for generating creative design concepts (Han et al.,
2020; Georgiev et al., 2010; Chiu and Shu, 2012b). Nagai et al. (Nagai et al.,
2009), in a collaboration with designers, suggested that a new concept can be
created by synthesizing two ideas in noun-noun combination phrases. Chiu and
Shu (Chiu and Shu, 2012b) used oppositely and similarly related pairs of words
as stimuli for design-concept generation and observed that oppositely related
verb-verb combination stimuli could increase concept creativity. Combinator
(Han et al., 2016) imitates the way the human brain achieves combinational
creativity and suggests combined ideas in both visual and textual
representations. However, in these pieces of research, combinational
creativity focused either on combined product categories, derived from noun-
noun combinations (e.g., “desk + elevator” or “pen + ruler”) or functional
features derived from verb-verb combinations (e.g., “fill + insert”), and it
did not address product aesthetics. In this paper, we aim to generate
combinational creativity as adjective-adjective (or noun, e.g., “kinetic +
warm(th)”) forms. To check this, we conducted a preliminary study comparing
the effects between noun-noun, verb-verb, and adjective-adjective (adjective-
noun) forms of phrase.

###  2.3. Utilizing lexico-semantic features in concept generation

In relation to the method used in this study, we focus on two key features:
word frequency and cosine distance between words. Setchi et al. (Setchi et
al., 2011a, b) used term frequency-inverse document frequency (TF-IDF)
measurement to identify the most meaningful words around an image and added
new tags to it with terms retrieved by semantic expansion from the original
terms. The method demonstrated that a term with a low document frequency in a
corpus could support richer inspiration and creativity for automotive
designers. Han et al. (Han et al., 2019; Han et al., 2018) analyzed the
conceptual distances between two ideas expressed in words (base and additive)
that were incorporated in each of 200 award-winner product-design descriptions
and measured the correlations between the distance of two words and expert
designers’ objective evaluations in ranking creativity. The result showed that
good design concepts fell into a certain range of distance between two ideas.
Also, a comparative study on using different language models to measure the
conceptual distances between two ideas suggested that ConceptNet best agrees
with human experts’ judgement on concept distances (Han et al., 2020). In
D-Graph, we also use the frequency and cosine distance. What is unique about
our method is that it uses them in a sequence to control the quality of the
combinational adjectives as well as searches for contrasting concepts
(antonyms) for each to help the user explain design concepts in terms of how
and by which attributes they differ.

##  3\. Method

###  3.1. Preliminary study

We decided to exclude noun-noun combinations to avoid words like “desk-
elevator,” which suggests a “mashup” of two objects rather than collectively
expressed product aesthetics. Meanwhile, adjective-noun combinations can be
used as long as the second word is a noun form of an adjective so that it
forms a compound adjective in a restrictive sequence - a sequence in which an
adjective restricts another adjective that follows (Sopher, 1962). As in the
example of “kinetic warmth” introduced earlier, conversion to a noun can be
done afterwards to abbreviate the noun to be modified. Yet, we needed to know
whether adjective phrase would work better over others, so we conducted a
preliminary experiment comparing phrases with different parts-of-speech (PoS)
so that we could be confident that adjective-adjective combinations are
suitable for communicating product aesthetics over other PoS. We used Survey
Monkey to recruit 55 participants from the U.S. whose job function is “Arts
and Design.” Six sample phrases were randomly generated for each of four
different combinations of PoS: adjective-adjective (AA), adjective-noun (AN),
noun-noun (NN), and verb-verb (VV). The participants rated 24 randomly
generated two-word combinational phrases in randomized order on a 7-point
Likert scale on the basis of the degree to which they agreed with the
statement “I can imagine the product aesthetics, characters, mood, and
emotional quality that are conveyed by the product design.” An ANOVA-Tukey
test identified homogeneous subsets as [AA/AN/NN] and [VV/NN], where the mean
score of the former was significantly higher $(p=0.05)$.

The further details of the individual comparisons are as follows. There was a
significant difference $(p=.038)$ in mean scores between AA
$(3.890,\sigma=1.121)$ and VV $(3.300,\sigma=1.205)$ , a significant
difference $(p=.040)$ between AN $(3.885,\sigma=1.025)$ and VV , no
significant difference $(p=.581)$ between AA and NN $(3.612,\sigma=1.232)$ ,
no significant difference $(p=.599)$ in between AN and NN , no significant
difference $(p=.485)$ between NN and VV , and no significant difference
$(p=1.000)$ between AA and AN. We randomly extracted the words for all
combinations from a corpus we created with English automotive design articles
containing about 1.4 million words on Sketch Engine(Kilgarriff et al., 2004).
The following filtration was performed equally to all PoS combinations. First,
we removed non-English terms and proper nouns, then removed words, whose
relative frequency per a million tokens was less than 1.0, compared to
enTenTen15 (Jakubíček et al., 2013), a large web text corpus containing about
1.6 billion words. This makes the list of all words, regardless of PoS, more
suitable for design concept expressions that participants can readily
recognize and make a judgement.

###  3.2. System and UI

Figure 2. D-Graph (experiment) web UI with 2-A participant’s character space
and word pool replicated for analysis purpose

Figure 3. Baseline web tool without D-Graph UI and search algorithm. We used
the Merriam Webster online thesaurus instead. Replicated screen from 5-B
participant’s character space and word pool for analysis purpose.

nimble aid/sustainable renewable

The algorithm of D-Graph searches for and filters adjectives that are related
to users’ queries by using a ConceptNet knowledge graph (Speer et al., 2017).
ConceptNet is a multilingual knowledge graph that connects words and phrases
with labeled edges, and it has the most extensive relations of edges over
other commonly available knowledge graphs. The top section of the web UI has a
design brief and a search window. The large space below them is allocated to a
“playground,” in which graphs of explored words are visualized in 3D hub-and-
spoke style. Users can examine the words at different granularities by zooming
in/out, rotating, and panning the graph. Every time the user expands the
search by clicking words, new clusters are shown in different colors so that
users can visually track back to previous explorations. A word definition can
be seen by mousing over the words. The lower-right section is a “word pool”
where users can store favorite words as candidates for design concept phrases.
Every time the user puts a query in the search window, clicks on a word in the
playground, or drags & drops words from the playground to the word pool, those
words are stored in the word pool. Finally, the right-middle section is the
character space (CS), which consists of two semantic differentials
orthogonally crossing each other. The CS is completed when all four ends on
the axes are defined as word 1 ($w_{1}$), word 2 ($w_{2}$), word 3 ($w_{3}$),
and word 4 ($w_{4}$). The words on the CS can be set by dragging & dropping
words either from the word pool or directly from the graphs in the playground.
The upper-right quadrant, represented by the combination of $w_{1}$ and
$w_{2}$, is the target design-concept phrase. All the other quadrants,
represented by $w_{2}$/$w_{3}$, $w_{3}$/$w_{4}$, and $w_{4}$/$w_{1}$, are
contrasting concepts to be used by the users to explain the target design
concepts in comparison with opposing concepts.

###  3.3. System configuration

D-Graph consists of a front-end web application written in JavaScript, HTML,
and CSS and a back-end web server written in Python with a MySQL database
hosted on PythonAnywhere (PythonAnywhere, [n.d.]). D3.js (Zhu, 2013) is used
to visualize the graph data structure. MySQL database holds the data of word
embeddings from ConceptNet Numberbatch (Speer et al., 2017) and word
frequencies in enTenTen15 (Jakubíček et al., 2013), an English web corpus
retrieved via Sketch Engine (Kilgarriff et al., 2014).

###  3.4. Search and filter algorithms

D-Graph directs users to set words on the CS in a predetermined order
($w_{1}$, $w_{2}$, $w_{3}$, then $w_{4}$). This strategy mandates that users
first establish the target design concept, represented by the upper-right
quadrant (blue square shown in Fig. 2) defined by $w_{1}$ and $w_{2}$,
followed by the contrasting concepts (all other quadrants shown in pink in
Fig. 2) that can be used in a “not this, but this” style of explanation.
D-Graph has two types of search and filter algorithms,
SEARCH_FOR_RELATED_WORDS (Algorithm 1) and SEARCH_FOR_ANTONYMS (Algorithm 2).
The former gets a new word $w^{\prime}$ from all nodes inside the edge $e$,
whose relation to the query $w$ is NOT “Antonym.” This means it uses all other
33 relations in ConceptNet in order to maximize the number of words retrieved.
Then, each new word $w^{\prime}$ from the nodes will be filtered in terms of
both the relative word frequency($Freq$) of $w^{\prime}$ (number of
occurrences per one million tokens in the enTenTen15 English corpus) and the
cosine similarity ($cosSim$) between the query word $w$ and the new word
$w^{\prime}$, calculated with ConceptNet Numberbatch word embeddings. After
several tests, we currently set the threshold at $(.05\leq|cosSim|\leq.5)$ and
$(1\leq Freq\leq 50)$. The latter (Algorithm 2) first gets related words with
the former algorithm; then, for each new word $w^{\prime}$, it gets all the
nodes in the edge whose relation to $w^{\prime}$ is “Antonym.” All the results
are set in the D3.js as labels of the start node and end node and the link
between them to render the graph.

Algorithm 1 Search for Related Words

function search_for_related_words($w$)

Initialize $results$ = []

for each edge $e$ for word $w$ in ConceptNet do

if relation of $e$ is not “Antonym” then

$w^{\prime}$ := get_other_word($e$, $w$)

$cosSim$ := get_cosine_similarity($w$, $w^{\prime}$) from
ConceptNetNumberBatch

$Freq$ := get_relative_frequency($w^{\prime}$) from SketchEngine

if $(0.05\leq|cosSim|\leq 0.5)\bigwedge(1\leq Freq\leq 50)$ then
$results$.append($w^{\prime}$) end if

end if

end for

return $results$

end function

Algorithm 2 Search for Antonyms

function search_for_antonyms($w$)

Initialize $results$ = [].

Initialize $related\\_words$ = SEARCH_FOR_RELATED_WORDS($w$)

for each word $w^{\prime}$ in $related\\_words$ do

for each edge $e$ for word $w^{\prime}$ in ConceptNet do

if relation of $e$ is “Antonym” then

$s$ := get_start($e$)

if $s$ is not in $results$ then $results$.append($s$) end if

$d$ := get_end($e$)

if $d$ is not in $results$ then $results$.append($d$) end if

end if

end for

end for

return $results$

end function

##  4\. Experiment Design

###  4.1. Participants and independent variables

Eleven undergraduate/graduate students (10 M, 1 F), who specialize in
automotive design in an industrial design department were, recruited.
Unfortunately, the only female participant’s responses became invalid due to
an inadequate task environment, which left us 10 all-male valid participants,
with a mean age of 25.1 years ($sd=4.01$). The independent variables were two
different search tools, D-Graph (Fig. 2) and the baseline tool (Fig. 3) using
the Merriam-Webster online thesaurus (Webster, 2014). As mentioned above,
D-Graph consists of search and filter algorithms with a 3D graph visualizer.
The UI of the search window, word pool, and CS [of the two tools?] were the
same, except for the word set order algorithm in D-Graph. The participants
were asked to perform the same task twice with the baseline and experimental
tools in a counterbalanced order (Table 1). They participated in the
experiment online using Playbook UX, a usability testing platform that enables
screen and “think-aloud” audio recordings. Each participant was given a video
instruction explaining the goal of the task and how to use each tool before
the task. They were also given a practice time window (2-3 min.) to get
familiar with how to operate the tools between the video instruction and
actual experiment.

###  4.2. Stimuli and tasks

All participants were provided with two different design briefs (Table 2). A
design brief is a written description of a project that requires some form of
design, containing a project overview, its objectives, tasks, target audience,
and expected outcomes (Phillips, 2004; Koronis et al., 2018). The two briefs
were also given to the participants in a counterbalanced order (Table 1).
After reading the brief, the participants were prompted to start the task.
First, they were asked to find a combination of two words that forms a DCP by
determining $w_{1}$ and $w_{2}$; then, they were asked to find the opposing
concept to each of $w_{1}$ and $w_{2}$ to generate the CS (Krippendorff,
2005). The session was concluded when the user was satisfied with the design
concept phrase in terms of $w_{1}$ and $w_{2}$ and comfortable explaining it
in contrast to the other three quadrants.

Table 1. Counterbalanced task arrangement

Task | Group 1 ($N=5$) | Group 2 ($N=5$)
---|---|---
1 | Exp.+ D.brief A | Cont + D.brief B
2 | Cont+ D.brief B | Exp. + D.brief A

Table 2. Two variations of design brief A(Setchi et al., 2011b): |  | Imagine a car for the megalopolis of
---
tomorrow and consider four important aspects:
environmental friendliness, social harmony,
interactive mobility, and economic efficiency.
B(Koronis et al., 2020): |  | Design a vehicle to improve mobility for
---
low-income individuals with physical disabilities.
Help the user move independently across difficult,
uneven, narrow or inclined terrain. (modified)

###  4.3. Quantitative measurement - dependent variables

####  4.3.1. Subjective evaluation

A post-task questionnaire with self-reported evaluations was administered
using a 7-point Likert scale for three measurements: “originality” of the DCP,
“relevancy” of the phrase to the design brief, and the “explainability” of the
DCP. The participants were asked to write a short explanation of the DCP
(upper-right quadrant of the CS), in contrast to the ideas expressed in the
other quadrants. This was measured by a 7-point Likert scale on how
comfortable they were in explaining the DCP.

####  4.3.2. Objective evaluation

Since this study is highly domain specific, the evaluation should also be done
by the consensus of expert raters(Shah et al., 2003). Two former executives in
the automotive design field who have led global design teams were recruited.
They were asked to rate each design concept phrase in a randomized order while
being blinded about which of the tools were used to generate each DCP. 7-point
Likert scales were used for the “originality” of the DCP, “relevancy” of the
DCP to the design brief, and the “imageability” of the DCP for the degree to
which they could imagine the design of the vehicle described with this design
concept phrase. The inter-rater reliability using Cohen’s kappa coefficient on
the metrics above were $k=.352,(p=.011),k=.159(p=.184),k=.215(p=.065)$,
respectively.

####  4.3.3. Computational metrics

The relative word frequency ($Freq$) of both $w_{1}$ and $w_{2}$ for each DCP
as well as the cosine similarity ($cosSim$) between them were calculated post-
hoc. The duration of the task and the word count in the “word pool,” which
indicates how many words the participant interacted with in the task, were
also retrieved. In addition, we measured the Pearson’s correlations between
the experts’ ratings on “originality” and the linguistic metrics above. We
further analyzed how selected participants interacted with the words using
spacial mapping based on the word embedding.

###  4.4. Qualitative data

All the DCPs and two other words on the CS (Table 6), as well as the written
explanations, were obtained. We also had the screen recordings of all sessions
as well as the think-aloud protocols. The participants were asked to verbalize
their thoughts during the session. The think-aloud protocols were hand-coded
and summarized. Video recording was analyzed to acquire insights on how the
participants actually utilized the tool overall, including the participants
strategy, mental model, usability issues, and how they should be addressed in
the future development.

##  5\. Results

###  5.1. Quantitative measurement

####  5.1.1. DCPs evaluation by participants results

No significant differences were found between the D-Graph and the baseline
tool in participants’ subjective evaluations on DCPs (Table 3).

####  5.1.2. DCPs evaluation by experts results

No significant differences were found between the D-Graph and the baseline
tool in experts’ objective evaluations on DCPs.

####  5.1.3. Computational Metrics

No significant differences were found on the task duration and word count in
the word pool (Table 4). Table 5 shows all the DCPs with the participant ID
with the type of design brief (A/B) , the tool used, the word count (WC) in
the word pool, the relative word frequency($Freq$) of both $w_{1}$ and
$w_{2}$, and the mean between the two in each DCP, as well as the cosine
similarity ($cosSim$) between them. Some words did not return a value due to
the unavailability of them in the word embeddings or in the corpus. There were
no significant differences $(p=.218)$ in mean $cosSim$ between the D-Graph
$(.246,\sigma=.195)$ and the baseline tool $(.149,\sigma=.124)$ and no
significant difference $(p=.154)$ in the mean of mean-$Freq$ between the
experiment tool $(26.42,\sigma=20.76)$ and the baseline tool
$(13.73,\sigma=15.61)$.

Interestingly, there was a moderate negative Pearson correlations
$(-.632,p=.004)$ between $cosSim$ and the experts’ objective evaluation on
“originality,” and a high negative Pearson correlations $(-.758,p\leq.001)$
between mean-$Freq$ and the experts’ objective evaluation on
“originality.”(Figure.4) No such significant correlations were found between
the same linguistic metrics above and the participant’s subjective
evaluations. We also examined how the participants interacted with the words,
got the words in the word pool, and decided $w_{1}-w_{4}$ along with the
computational linguistics metrics. We will present summaries of four cases in
this paper. Fig. 6 shows the participant’s exploration process where circled
numbers are the sequence of the interactions. The words are mapped according
to the the ConceptNet Numberbatch word embeddings, whose dimensionality is
reduced by principal components analysis (PCA). The blue areas show searches
for DCPs for $w_{1}$ and $w_{2}$, and the pink areas show searches for
antonyms for $w_{3}$ and $w_{4}$, $w_{3}$.

Case 1-B:“protean companionable” (Fig.6-(a)) had a $cosSim$ value of $0.063$,
the smallest $meanFreq$ was $0.13$, created with the baseline tool responding
to the design brief B. The experts “originality” score marked $6.5$. The
number of the words in the word pool was $20$ and the task duration was 12
minutes and 59 seconds. He started with ‘versatile,’ and typed the next three
words without clicking on the words in the thesaurus, then found ‘protean’ in
the thesaurus. He then restarted the search by typing ‘companionable,’ then
found the next three words in the thesaurus. Then he put ‘affordable’,
mentioning “…now I come back to a kind of basic” and found the next four words
in the thesaurus. At this point, he had already decided to put
$w_{1}$(“protean”) and $w_{2}$ (“companionable”) for the DCP, and started
exploring antonyms. He found ‘limited’ as an antonym of ‘protean’ and found
the next four words in the thesaurus. He relied on his own judgement of the
first four queries and started to interact with the thesaurus more except for
two “fresh starts” on ‘companionable’ and ‘affordable’. His own ratings for
“originality” and “relevancy” were $5$ and $7$.

Case 1-A:“cognizant inclusive” (Fig.6-(b)) was made by the same participant
above using the D-Graph responding to the design brief B. It has a $cosSim$
value of $0.105$, the $meanFreqwas(10.37)$. The experts “originality” score
marked $5.0$. The number of the words in the word pool was $23$ and the task
duration was 14 minutes and 58 seconds. He typed the first word ‘amiable’ and
used manual search window, instead of clicking the words on the graph, until
he found the sixth word, ‘visionary’ on the D-Graph. During that time, he
opened a new tab on the browser and used an online thesaurus to find the
adjective form of ‘utopia’ as it was denied by the system because ‘utopia’ was
not an adjective. Then the words he explored aimed to express “being aware of
the social issues”. He also noted,“Desirable for sure, but that’s given.” By
the time he stored the 16th word (‘citywide’) in the word pool he decided to
use ‘cognizant’ and ‘inclusive’ for the DCP. Putting ‘cognizant’ on $w_{1}$
triggered showing the candidates for $w_{3}$, he found ‘oblivious’, and
dropped it to $w_{3}$ as he noted, “that’s a good word.” It triggered showing
the candidates for $w_{4}$, but it showed only four words, including the root
node(‘inclusive’, ‘micro’, ‘exclusionary’, and ‘exclusive.’ He tried ‘micro’
anyway, but he did not find anything he liked. So he went back to ‘inclusive’
by clicking it, and clicked on ‘exclusive’ that gave him eighteen new words.
After examining all words there he dragged and dropped ’selective’ to $w_{4}$.
His own ratings for “originality” and “relevancy” were $4$ and $7$.

Case 2-A: “sustainable renewable” (Fig.6-(c)) was made using the D-Graph
responding to the design brief A. It has a $cosSim$ value of $0.572$, the
$meanFreqwas(66.74)$ The experts “originality” score marked $1.5$. The number
of the words in the word pool was $5$ and the task duration was 1 minutes and
23 seconds. Given the small numbers of words in the word pool the participants
interacted for the next two cases, we will also present the number of words
added when a word was clicked in the playground in parentheses, retrieved from
the JavaScript console in a replicated session. He first typed
‘sustainable’($6$) in the search window after reading the design brief that
showed six candidates for $w_{1}$. Then he clicked ‘renewable’ ($5$), then
‘continuous’ ($17$), ‘imperfect’ ($14$), and, finally, ‘flawed’ ($1$). Once
‘continuous’ was clicked, it took him only 14 seconds to click the latter
three words. He dragged and dropped ‘sustainable’ for $w_{1}$, followed by
‘renewable’, ‘imperfect” and ‘flawed’ for $w_{2}$, $w_{3}$, and $w_{4}$,
respectively. In this session we observed the participant put all the words at
once in $w_{1}$ through $w_{4}$, where the new search for distant word for
$w_{2}$, as well as antonym searches triggered by setting $w_{2}$ and $w_{3}$,
were not utilized. Since he used the first two words including his own query,
the $cosSim$ value between two words were among the largest. His own ratings
for “originality” and “relevancy” were $4$ and $7$.

Case 7-B: “economical efficient” (Fig.6-(d)) was made using the D-Graph
responding to the design brief B. It has a $cosSim$ value of $0.551$, the
$meanFreqwas(31.64)$ The experts “originality” score was $2.5$. The number of
the words in the word pool was $6$ and the task duration was 7 minutes and 1
second. After reading the design brief, he typed ‘economical’($5$) in the
search window that showed five words. After clicking on ‘efficient’($18$) and
‘capable’($25$) he spent a minute and forty seconds to rotate the graph and
mouse-overed several words to see the definitions, click ‘efficient’ and
‘capable’ twice each, then finally cleared the playground and typed
‘economical’ again, followed by clicking ‘efficient.’ Then he clicked
‘futile’, but it was apparently accidental as he deleted ‘futile’ soon and
cleaned up the playground again. He typed and clicked ‘efficient’ , ‘capable’,
and ‘capable’ for the third time. Before clicking the next one,
‘resourceful’($5$), he carefully examined the definition of ‘competent’,
‘thorough’ and ‘resourceful.’ Then he spent twenty seconds to see the
definition of ‘ingenious’, pause another ten seconds to click
‘ingenious’($5$), followed by ‘natural’($5$) in fifteen seconds. He further
spent fifty-two seconds to rotate the graph, clicked ‘capable’ and
‘resourceful’ again, then put ‘economical’, ‘efficient’, ‘capable’, and
‘resourceful’ for $w_{1}$, $w_{2}$, $w_{3}$, and $w_{4}$, respectively. His
own ratings for “originality” and “relevancy” were $6$ and $7$.

Table 3. Subjective evaluation results

| Mean rating ($N$=10) |
---|---|---
Variable | Base.( $\sigma$ ) | Exp.( $\sigma$ ) | $p$
Originality | 5.1(0.99) | 5.4(1.43) | 0.591
Relevancy | 5.5(1.51) | 6.1(0.99) | 0.217
Explainability | 5.4(1.65) | 5.9(1.45) | 0.427

Table 4. Objective evaluation results | Mean rating ($N$=2) |
---|---|---
Variable | Base.( $\sigma$ ) | Exp.( $\sigma$ ) | $p$
Originality | 4.55(1.32) | 3.95(1.72) | 0.394
Relevancy | 4.95(0.64) | 4.90(0.96) | 0.893
Imageability | 4.45(1.30) | 4.35(0.97) | 0.848
Duration(min.) | 9.02(3.76) | 8.68(4.47) | 0.888
W. Count in WP | 8.7(5.27) | 12.2(6.00) | 0.183

Table 5. Design concept phrases generated by participants P. ID | Tool | $w_{1}+w_{2}$ | $WC$ | $Freq(w_{1})$ | $Freq(w_{2})$ | mean$Freq$ | $cosSim(w_{1},w_{2})$
---|---|---|---|---|---|---|---
1-A | Exp. | “cognizant inclusive” | 23 | 1.02 | 19.72 | 10.37 | 0.105
2-A | Exp. | “sustainable renewable” | 5 | 97.59 | 35.89 | 66.74 | 0.572
3-A | Exp. | “honest continuous” | 22 | 22.25 | 30.06 | 26.15 | 0.123
4-A | Exp. | “futuristic modern” | 10 | 2.22 | 108.15 | 55.19 | 0.392
5-A | Exp. | “august renewable” | 10 | 2.08 | 35.89 | 18.99 | 0.021
7-B | Exp. | “economical efficient” | 6 | 6.32 | 56.97 | 31.64 | 0.551
8-B | Exp. | “affordable neutral” | 13 | 42.35 | 12.40 | 27.38 | 0.068
9-B | Exp. | “modular disposable” | 10 | 7.16 | 4.27 | 5.71 | 0.162
10-B | Exp. | “empathy transcendent” | 19 | null | 1.45 | 1.45 | 0.240
11-B | Exp. | “utilitarian comfortable” | 11 | 1.13 | 40.05 | 20.59 | 0.235
7-A | Base. | “efficient functional” | 4 | 56.97 | 33.92 | 45.45 | 0.382
8-A | Base. | “good-natured safeness” | 8 | null | null | null | null
9-A | Base. | “adventurous lively” | 5 | 3.82 | 10.20 | 7.01 | 0.284
10-A | Base. | “sustained delightful” | 7 | 8.58 | 6.24 | 7.41 | 0.047
11-A | Base. | “empathetic minimal” | 9 | 0.98 | 18.12 | 9.55 | 0.055
1-B | Base. | “protean companionable” | 20 | 0.17 | 0.09 | 0.13 | 0.063
2-B | Base. | “affordable seamless” | 6 | 42.35 | 6.16 | 24.26 | 0.185
3-B | Base. | “insensible trustful” | 16 | 0.20 | 0.16 | 0.18 | 0.200
4-B | Base. | “compact friendly” | 5 | 12.77 | 43.70 | 28.24 | 0.121
5-B | Base. | “nimble aid” | 8 | 1.36 | null | 1.36 | 0.007

(a)

(b)

Figure 4. (a) Pearson correlations between cosine similarity $(w_{1},w_{2})$
and experts’ evaluation on “originality.” (b) Pearson correlations between
mean mean-frequency $(w_{1},w_{2})$ and experts’ evaluation on “originality.”

Figure 5.

Figure 6. Sequence for word exploration in semantic space. Words were mapped
according to dimensionality reduction by principal components analysis (PCA)
based on ConceptNet Numberbatch word embedding. Blue areas show searches for
DCPs for $w_{1}$ and $w_{2}$, and pink areas show searches for antonyms for
$w_{3}$ and $w_{4}$. Red circles are users’ own queries. Blue circles are
users’ clicks on words.

###  5.2. Qualitative results

####  5.2.1. Words on character space and explanations

All the DCPs, $w_{3}$ and $w_{4}$ on the CS, participants’ “explainability”
scores, as well as authors’ observation on whether or not the explanation
contains comparative descriptions using the concepts of $w_{3}$ and/or $w_{4}$
are shown on Table 6. Only the case 9-A:“adventurous lively” and 5-B:“nimble
aid” was explained in the way we had hoped the participants would perform. 9-A
participant explains his concept as ‘The design concept phrase of “adventurous
lively“ speaks to the want we all have within to go out and discover new
things around us with the ones we care about in a communal environment while
the other concepts within the chart relate to the being more stationary and in
a mellowed out environment for either self reflection or simple relaxation.’
5-B participant explains “‘Nimble Aid” represents a combination of the agility
required in the brief with overall intention of helping, whereas other phrases
focus on economic or level of determination.’

####  5.2.2. Utilization and the search algorithms

As described in the section 5.1.3, the participant on case 1-A, who created
“cognizant inclusive”, had chosen $w_{2}$ from the word pool, so he did not
utilize the SEARCH_FOR_RELATED_WORDS (Algorithm 1). Yet, he was able to pick
two words that are distant enough to get a high “originality” score by the
expert. He actually set the $w_{3}$ and $w_{4}$ with the words from the
playground, that were the output according to the $w_{1}$ and $w_{2}$ using
SEARCH_FOR_ANTONYMS (Algorithm 2). This was what we had assumed how users
would use the D-Graph and incorporated in the instructions to the participant.
However, our video analysis unveiled there were only two cases (4-A and 5-A)
that utilized the former algorithm and three cases (1-A, 4-A and 5-A) that
utilized the latter algorithm to explore the words.

####  5.2.3. Summary of qualitative analysis

The analysis think-aloud protocol and screen recording uncovered variety of
insights for future development and search strategies. Below are summary of
insights we would like to highlight for future development, categorized in
three-fold, addressing usability issues, accommodating user’s mental model,
and reflections on their own DCPs, as well as on D-Graph tool.

Usability issues: First, many pointed out issues in transparency of the
process and system status especially from those who were aware of the
difference in phased search algorithms and tried to utilize them (1-A, 4-A,
5-A participants). It was unclear which of the two search algorithms,
SEARCH_FOR_RELATED_WORDS or SEARCH_FOR_ANTONYMS, was running especially when
users want to change some words on the axes on the CS. The weakness of the
ConceptNet in showing clear antonyms also contributed to this issue. 1-A
participant suggested we iterate the color system to make distinction between
different search mode. In contrast to the antonyms, some participants (10-A,
2-A, 8-A) seemed to be overwhelmed by the vast number of words exploded on the
D-Graph, making them difficult to recognize all words there. However, the
opinions varied depending on individual comfort level. The familiar list of
Merriam Webster thesaurus gave these users more peace of mind, where as some
participants (5-A, 7-A, 11-A) were excited about the novelty of UI, stating
“this is more interesting than the first tool. It’s easy to use as all the
lines are branches showing the relationship between different words” (7-B).
Another major feedback was on the restriction of D-Graph, which does not
accept non-adjective queries. (1-A, 5-A, 10-A). In fact, no one complained
about the output DCP being adjective-adjective, but the search should not
block non-adjective query. 1-A participant actually has to look up an
adjective form of “utopia” on another online dictionary before putting it into
the D-Graph. Lastly, many wished they could swap the words on the CS axes. It
was, again, restricted due to the search strategy for two different search
algorithm until they set all words. Even after setting all words, swapping
words between axes were not allowed. 3-B participant said, “I need to have my
own logic in making a character space. Even if I find a new word, I could not
shuffle, which bothers me.”

Accommodating users’ mental model: We acknowledge that there are different
mental models of the users the tool need to accommodate. Some of the
participants had clear ideas of what a good DCP (some people called them ‘key
words’) consist of, and had opinions on how they achieve it. 10-A/B
participants incisively pointed out, “this is good key words because two words
are serving for different aspects of the design brief.” As a strategy, 1-A
participants told us his one technique, described as “I usually use a simple
query word plus ‘definition’ on google search, that gives me a bunch of list
that contains a couple of complicated words, then I put those uncommon words
on thesaurus.com to look up more nuanced options.” This participant actually
performed the same way on in creating “definition” on Fig. 6(a). After
exploring some fairly uncommon words, such as “amicable”, “cordial”, and
“harmonious”, he restarted the search with “affordable”, mentioning “now I
want to come back to a basic one.” Apparently he knew when to exploit and when
to explore. As such, our tool needs to accommodate the mental model they
already formed, as well as that of some novice users. In the section 5.1.3, we
highlighted the long intervals participant 2-A had to take between searches to
look up word definition, which by the way lots of participants appreciated,
and ended up setting the first two words he found on the CS. Having seen that,
creating a search strategy is one problem, but making the participants aware
of the strategy is another problem we would need to address.

Participants’ reflection of the DCPs and D-Graph tool: While the participants
were asked to rate their self-reported quality of the DCP in “originality”,
“relevancy” and “explainability” they had mixed reflections on what they have
created. 1-A participant initially mentioned the idea of forming a DCP did not
really make sense because it was just a combination of two adjectives together
after all. But after he finished his task, he stated. “I never thought up
these combinations, but (when presented) it really can be something.” 11-A
participant pointed out they would need to think more with visuals, which we
did not incorporate into the study this time. They noted, “thinking about
concept only by words are still not enough. I need some visual support
although overall it is very fun tool to play with to see all related words.”
We did not measure engaging factors on the tool because it was outside of our
scope on this study, however, it should be noted some participants expressed
it was fun to interact with. Our rational on the graphical representation was
rather for a functional purpose, making it easier for the users to go back and
forth in different granularity in the semantic space. We did observed some
participants, like 2-A went back to the previous nodes several times to
examine the direction for further explorations.

Table 6. Words on CS, explainability rating by participants, Contrasting explanation (Con.exp.) P. ID | Tool | $DCP(w_{1}+w_{2})$ | $w_{3}$ | $w_{4}$ | $Explainability$ | Con. exp.
---|---|---|---|---|---|---
1-A | Exp. | “cognizant inclusive” | “oblivious” | “selective” | 7 | No
2-A | Exp. | “sustainable renewable” | “imperfect” | “flawed” | 7 | No
3-A | Exp. | “honest continuous” | “attached” | “instant” | 7 | No
4-A | Exp. | “futuristic modern” | “ordinary” | “elite” | 3 | No
5-A | Exp. | “august renewable” | “civil” | “admirable” | 4 | No
7-B | Exp. | “economical efficient” | “capable” | “resourceful” | 7 | No
8-B | Exp. | “affordable neutral” | “comfortable” | “independent” | 6 | No
9-B | Exp. | “modular disposable” | “secure” | “easy” | 5 | No
10-B | Exp. | “empathy transcendent” | “conscious” | “trustworthy” | 6 | No
11-B | Exp. | “utilitarian comfortable” | “economic” | “intelligent” | 7 | No
7-A | Base. | “efficient functional” | “dynamic” | “kinetic” | 3 | No
8-A | Base. | “good-natured safeness” | “comfortable” | “practical” | 5 | No
9-A | Base. | “adventurous lively” | “serene” | “calm” | 3 | Yes
10-A | Base. | “sustained delightful” | “authentic” | “modest” | 6 | No
11-A | Base. | “empathetic minimal” | “modular” | “sustainable” | 7 | No
1-B | Base. | “protean companionable” | “bounded” | “inhospitable” | 7 | No
2-B | Base. | “affordable seamless” | “special” | “discount” | 5 | No
3-B | Base. | “insensible trustful” | “active” | “regular” | 7 | No
4-B | Base. | “compact friendly” | “streamlined” | “dreaming” | 4 | No
5-B | Base. | “nimble aid” | “resolute” | “provident” | 7 | Yes

##  6\. Discussion and Future Work

Our experiment did not demonstrate an advantage of the D-Graph in creating an
original DCP for automotive design concept creation task in comparison with
the baseline tool. However, we observed a clear correlations between the
expert’s objective evaluations on DCPs and the computational linguistic
measurements using the ConceptNet knowledge graph, the ConceptNet Numberbatch
word embeddings and the enTenTen15 English web corpus. Our strategy was
aligned with our goal, but the strategy could not be effectively implemented.
We closely examined how our participants interacted with the tool and words.
One notable finding was that the high-performers interacted not just with more
words, but they also interacted with nuanced words in a semantic space. Their
strategy was rather a convergence rather than a divergence when examining
words to choose from while most inquiries in creative support tools mainly
focused on divergent thinking (Silvia et al., 2013). Our approach may be a bit
confusing because on one hand we aim to maintain a distance between two
concepts represented by $w_{1}$ and $w_{2}$, while on the other hand we try to
support users to find nuanced words once the target semantic is set. In the
future study we will add more clarity on what strategy we want to help the
users to follow, while still encouraging a sense of creative freedom which
designers definitely want to maintain. One intention is to implement more
automated function we did not implemented at this time round. For instance,
extracting words from the design brief and convert non-adjective words to
adjective can be automated, and would lower the initial barrier of
explorations especially for inexperienced designers. Automated query
generations would trigger variety of candidate at the beginning of the search.
Also, the presentation of the candidates word can be more intentional having
observed it was not easy for some users to avoid cliché words. Rather than
presenting words on 3D graph, it is worth trying an organized list of words
that are ranked according to the computational linguistic metrics proven to be
correlate with the quality of DCPs. We could further automate the process of
concatenating two adjectives in a way they maintain certain distance we
discussed in this paper. While it is still unclear what type of adjectives
works better to express a product aesthetics we aim to communicate, we may
need to further classify adjectives in different supersense(Tsvetkov et al.,
2014), witch is known to predict more of an abstract meanings of a word.
Finally, we should be investigating more of fun and engaging factors(Cherry
and Latulipe, 2014), that we did not measure in this study, while creativity
definitely need to be activated by human cognition.

##  7\. Conclusion

We created an AI-assisted interactive tool, D-Graph, aiming to help designers
exploring the nuanced concepts optimizing creative outcomes in verbalizing
design concept during an early stage of an automotive design project. We
integrated two language-based methodologies to attack the problem: 1)
utilizing compound adjectives to express aesthetic design concept, 2) search
and filter algorithms utilizing a ConceptNet knowledge graph, word-embedding-
based language model, and corpus query system. We also implemented a dynamic
3D graph visualization for intuitive interactions. Our experiment with 10
student participants did not indicate a significant advantage with our system
in comparison with the conventional online thesaurus. However, we confirmed
the metrics we used, the relative word frequency and the cosine similarity
between the compound words correlates with the experts objective evaluation on
“originality” of the DCPs. Our qualitative analysis found several important
aspects in how users interact with words in lexicosemantic space when
searching for nuanced words to create a distinguished design concept. As for
our reflections on potential social impacts our study would make, we
definitely acknowledge that our system is a recommender system, whose
performance may be biased depending on the algorithm and the data set from
which it is trained. While our study involves aesthetics, which is deeply
rooted in a notion of the society, we will contemplate the consequences of the
technology being implemented and disseminated. It is our responsibility that
we research and develop these technologies in the way humanity is enhanced
instead of perished.

##  8\. Acknowledgement

We appreciate the support of the Academy of Art University in San Francisco,
CA for referring the research participants.

## References

  * (1)
  * Bae et al. (2020) Suyun Sandra Bae, Oh-Hyun Kwon, Senthil Chandrasegaran, and Kwan-Liu Ma. 2020.  Spinneret: Aiding Creative Ideation through Non-Obvious Concept Associations. In _Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems_. ACM, US, 1–13.
  * Boden (2001) Margaret Boden. 2001\.  Creativity and knowledge.  _Creativity in education_ (2001), 95–102.
  * Bouchard et al. (2005) Carole Bouchard, Roger Camous, and Ameziane Aoussat. 2005\.  Nature and role of intermediate representations (IR) in the design process: Case studies in car design.  _International journal of vehicle design_ 38, 1 (2005), 1–25.
  * Chen et al. (2019) Ting-Ju Chen, Sai Ganesh Subramanian, and Vinayak R Krishnamurthy. 2019\.  Mini-map: Mixed-initiative mind-mapping via contextual query expansion. In _AIAA Scitech 2019 Forum_. 2347.
  * Cherry and Latulipe (2014) Erin Cherry and Celine Latulipe. 2014.  Quantifying the creativity support of digital tools through the creativity support index.  _ACM Transactions on Computer-Human Interaction (TOCHI)_ 21, 4 (2014), 1–25.
  * Chiu and Shu (2012a) Ivey Chiu and Li H Shu. 2012a.  Investigating effects of oppositely related semantic stimuli on design concept creativity.  _Journal of Engineering Design_ 23, 4 (2012), 271–296.
  * Chiu and Shu (2012b) I. Chiu and L. H. Shu. 2012b.  Investigating effects of oppositely related semantic stimuli on design concept creativity.  _Journal of Engineering Design_ 23, 4 (2012), 271–296.  https://doi.org/10.1080/09544828.2011.603298
  * Georgiev et al. (2010) Georgi V. Georgiev, Yukari Nagai, and Toshiharu Taura. 2010\.  A method for the evaluation of meaning structures and its application in conceptual design.  _Journal of Design Research_ 8, 3 (2010), 214–234.  https://doi.org/10.1504/JDR.2010.032607
  * Han et al. (2021) Ji Han, Hannah Forbes, and Dirk Schaefer. 2021.  An exploration of how creativity, functionality, and aesthetics are related in design.  _Research in Engineering Design_ (2021), 1–19.
  * Han et al. (2020) Ji Han, Min Hua, Dongmyung Park, Pan Wang, and PRN Childs. 2020.  Computational Conceptual Distances in Combinational Creativity. In _Proceedings of the Design Society: DESIGN Conference_ , Vol. 1. Cambridge University Press, 177–186.
  * Han et al. (2019) Ji Han, Dongmyung Park, Feng Shi, Liuqing Chen, Min Hua, and Peter RN Childs. 2019\.  Three driven approaches to combinational creativity: Problem-, similarity-and inspiration-driven.  _Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science_ 233, 2 (2019), 373–384.
  * Han et al. (2016) J Han, Feng Shi, PRN Childs, et al. 2016\.  The Combinator: A computer-based tool for idea generation. In _DS 84: Proceedings of the DESIGN 2016 14th International Design Conference_. 639–648.
  * Han et al. (2018) Ji Han, Feng Shi, Dongmyung Park, Liuqing Chen, Peter Childs, et al. 2018\.  The conceptual distances between ideas in combinational creativity. In _DS 92: Proceedings of the DESIGN 2018 15th International Design Conference_. 1857–1866.
  * Jakubíček et al. (2013) Miloš Jakubíček, Adam Kilgarriff, Vojtěch Kovář, Pavel Rychlỳ, and Vít Suchomel. 2013.  The TenTen corpus family. In _7th International Corpus Linguistics Conference CL_. 125–127.
  * Jansson and Smith (1991) David G Jansson and Steven M Smith. 1991.  Design fixation.  _Design studies_ 12, 1 (1991), 3–11.
  * Kilgarriff et al. (2014) Adam Kilgarriff, Vít Baisa, Jan Bušta, Miloš Jakubíček, Vojtěch Kovář, Jan Michelfeit, Pavel Rychlỳ, and Vít Suchomel. 2014.  The Sketch Engine: ten years on.  _Lexicography_ 1, 1 (2014), 7–36.
  * Kilgarriff et al. (2004) Adam Kilgarriff, Pavel Rychly, Pavel Smrz, and David Tugwell. 2004.  Itri-04-08 the sketch engine.  _Information Technology_ 105 (2004), 116.
  * Kita and Rekimoto (2018) Yui Kita and Jun Rekimoto. 2018.  V8 Storming: How Far Should Two Ideas Be?. In _Proceedings of the 9th Augmented Human International Conference_. 1–8.
  * Koch et al. (2019) Janin Koch, Andrés Lucero, Lena Hegemann, and Antti Oulasvirta. 2019.  Design Ideation with Cooperative Contextual Bandits.  (2019).
  * Koronis et al. (2018) Georgios Koronis, Arlindo Silva, Jacob Kang, et al. 2018\.  The impact of design briefs on creativity: A study on measuring student designers outcomes. In _DS 92: Proceedings of the DESIGN 2018 15th International Design Conference_. 2461–2472.
  * Koronis et al. (2020) G Koronis, A Silva, JKS Kang, and C Yogiaman. 2020\.  How To Best Frame a Design Brief To Maximize Novelty and Usefulness in Idea Generation. In _Proceedings of the Design Society: DESIGN Conference_ , Vol. 1. Cambridge University Press, 1745–1754.
  * Krippendorff (2005) Klaus Krippendorff. 2005\.  _The semantic turn: A new foundation for design_.  crc Press.
  * Lawson (2006) Bryan Lawson. 2006\.  _How designers think: The design process demystified_.  Routledge.
  * Nagai et al. (2009) Yukari Nagai, Toshiharu Taura, and Futoshi Mukai. 2009\.  Concept blending and dissimilarity: factors for creative concept generation process.  _Design Studies_ 30, 6 (2009), 648–675.
  * Phillips (2004) Peter L Phillips. 2004\.  _Creating the Perfect Design Brief: How to manage design for strategic advantage_.  Skyhorse Publishing Inc.
  * PythonAnywhere ([n.d.]) LLP PythonAnywhere. [n.d.].  PythonAnywhere Integrated Development Environment, Web Hosting Service. October, 2012.
  * Setchi et al. (2011a) Rossitza Setchi, Qiao Tang, and Ivan Stankov. 2011a.  Semantic-based information retrieval in support of concept design.  _Advanced Engineering Informatics_ 25, 2 (2011), 131–146.  https://doi.org/10.1016/j.aei.2010.07.006
  * Setchi et al. (2011b) Rossitza Setchi, Qiao Tang, and Ivan Stankov. 2011b.  Semantic-based information retrieval in support of concept design.  _Advanced Engineering Informatics_ 25, 2 (2011), 131–146.
  * Shah et al. (2003) Jami J Shah, Steve M Smith, and Noe Vargas-Hernandez. 2003\.  Metrics for measuring ideation effectiveness.  _Design studies_ 24, 2 (2003), 111–134.
  * Silvia et al. (2013) Paul J Silvia, Roger E Beaty, and Emily C Nusbaum. 2013\.  Verbal fluency and creativity: General and specific contributions of broad retrieval ability (Gr) factors to divergent thinking.  _Intelligence_ 41, 5 (2013), 328–340.
  * Sopher (1962) H Sopher. 1962.  Sequence of adjectives.  _ELT Journal_ 16, 4 (1962), 192–198.
  * Speer et al. (2017) Robyn Speer, Joshua Chin, and Catherine Havasi. 2017.  ConceptNet 5.5: An Open Multilingual Graph of General Knowledge.  (2017), 4444–4451.  http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14972
  * Tovey (1992) Michael Tovey. 1992\.  Intuitive and objective processes in automotive design.  _Design Studies_ 13, 1 (1992), 23–41.
  * Tsvetkov et al. (2014) Yulia Tsvetkov, Nathan Schneider, Dirk Hovy, Archna Bhatia, Manaal Faruqui, and Chris Dyer. 2014\.  Augmenting English adjective senses with supersenses.  (2014).
  * Webster (2014) Merriam Webster. 2014\.  Merriam-webster online.
  * Zhu (2013) Nick Qi Zhu. 2013\.  _Data visualization with D3. js cookbook_.  Packt Publishing Ltd.


In the rest of the subsection we fix a "sound resolver" $\resolv$ for $\A$ "implemented by@@resolvMem" a "memory structure@@aut" $\M=(M, m_\init, \transMem)$.
For simplicity, we assume that every pair of a state and a memory state $(q,m)$ is ""reachable using $\resolv$@@memory"", that is, there is some word $w\in \SS^*$ such that $ \rr = q_\init\lrpResolver{\resolv}{w} q$ and $\transMem(m_\init, \rr) = m$. It is easy to see that we can get rid of this assumption in the upcoming proof just by ignoring pairs $(q,m)$ that are not "reachable@@res".

For $(q,m)\in Q\times M$, we let $(q,m)\intro*\lrpResolverMem{\resolv}{w} (q',m')$ be the (unique) "run induced by $\resolv$" from $q$ when the memory structure is in state $m$.
We extend notations of the form $(q,m)\lrpExistsResolver{\resolv}{w:x} q'$ in the natural way; the previous one means that there exists $u_0\in \SS^*$ such that the induced run of $\resolv$ is $\rr = q_\init\lrpResolver{\resolv}{u_0} q$, $\transMem(m_\init, \rr) = m$ and $q_\init\lrpResolver{\resolv}{u_0w} q'$, producing priority $x$ in the second part of this run.

As $\A$ is "deterministic over" transitions using priorities $\geq x$, we may omit the subscript $\resolv$ in paths producing no priority $<x$.

Synchronising separating runs.

We first show that we can force to produce priority $x-1$ from $\classSig{x}{q}$, while remaining safe from $\classSig{x}{q}$.
There is a word $u\in \SS^+$ such that for all $s\in \classSig{x}{q}$:

\[s \lrpAllResolver{\resolv}{u:x-1} \,, \quad \tand\quad \classSig{x}{q'}\lrpAllResolver{\resolv}{u: x}\classSig{x}{p}.\]

By definition of the preorder $\leqSig{x}$, there is a word $u_1\in \SS^+$ such that for all $s\in \classSig{x}{q}$ and $s'\in \classSig{x}{q'}$, $s \lrpAllResolver{\resolv}{u_1:x-1}$ and $s'\lrpResolver{\resolv}{u_1:\geq x}$.
By "normality", we can extend this word so that $q'\lrpResolver{\resolv}{u_1':\geq x} q'$; by monotonicity of safe languages all runs from $\classSig{x}{q'}$ reading $u_1'$ go back to $\classSig{x}{q'}$.
Applying  Lemma <ref>, we obtain $u_2$ that "produces priority $x$ uniformly" in $\classSig{x}{q'}$ and goes to $\classSig{x}{p}$.
We take $u=u_1'u_2$, which satisfies $\classSig{x}{q'} \lrpResolver{\resolv}{u: x}\classSig{x}{p}$, and it produces at least one occurrence of priority $x-1$ from every state $s\in\classSig{x}{q}$.
By "$[0,x-2]$-faithfulness", a run $s \lrp{u}$ only produces priorities $\geq x-1$, which concludes.

Let $p' \eqSig{x-2} q$ and let $m\in M$ be a memory state. Then there is a word $w_{q,m}$ such that:

\[ (q,m)\lrpResolverMem{\resolv}{w_{q,m}:\geq x-1} \classSig{x}{p'}, \, \tand \;\;  \classSig{x}{p'}\lrpAllResolver{\resolv}{w_{q,m}: x}\classSig{x}{p'}.\]

We distinguish two cases. First, assume that $\safeSig{x}{q}\subseteq \safeSig{x}{p'}$. In this case, by "${<}x$-safe centrality" of $\A$, $q$ and $p'$ are in the same "${<}x$-safe component" so $q\eqSig{x-1}p'$ (and $q\leqSig{x}{p'}$).
Let $p'_{\max}$ be a state in $\classSig{x-1}{p'}$ such that $p'\leqSig{x}{p'_{\max}}$, and maximal with this property. Let $w_1\in \SS^*$ be a word such that $q\lrp{w_1:\geq x} p'_{\max}$ (which exists because these two states are in the same "${<}x$-safe component").
By monotonicity of "safe languages", $p'\lrp{w_1:\geq x} p''$ with $p'_{\max}\leqSig{x}p''$. By maximality of $p'_{\max}$, we must have $p''\eqSig{x}{p'_{\max}}$.
Finally, let $w_2\in \SS^*$ such that $p''\lrp{w_2:x} p'$ "producing priority $x$ uniformly in" the class $\classSig{x}{p''}$ (which exists by Lemma <ref>). We obtain $q\lrp{w_1:\geq x} p'_{\max} \lrp{w_2:x} \classSig{x}{p'}$ and $\classSig{x}{p'}\lrp{w_1:\geq x} \classSig{x}{p'_{\max}} \lrp{w_2:x} \classSig{x}{p'}$ as required.

Assume now that $\safeSig{x}{q}\nsubseteq \safeSig{x}{p'}$. In that case, we can find a word $w_1\in \safeSig{x}{p'}\setminus \safeSig{x}{q}$. By Lemma <ref>, we may assume that it "produces priority $x$ uniformly" from $\classSig{x}{p'}$ and comes back to this class.
Moreover, by "faithfulness", it cannot produce priorities $\leq x-2$ and respects the $\eqSig{x-2}$-classes. Thus:

\[ (q,m)\lrpResolver{\resolv}{w_1: x-1} (q_1,m_1), \text{ with } q_1\eqSig{x-2}p' \,, \tand \quad \classSig{x}{p'}\lrp{w_1:x} \classSig{x}{p'}. \]

If $\safeSig{x}{q_1}\subseteq \safeSig{x}{p'}$, we can conclude by using the first case.
While we do not have this inclusion, we build, using the argument above, a sequence of words $w_1,w_2,\dots $ such that:

\[ (q_i,m_i)\lrpResolver{\resolv}{w_i: x-1} (q_{i+1},m_{i+1}) \,, \tand \classSig{x}{p'}\lrp{w_i:x} \classSig{x}{p'}. \]

This sequence cannot be infinite.
If it were the case, resolver $\resolv$ would "induce@@resolv" a "rejecting run" over $w_1w_2\dots$ from $(q,m)$, and an "accepting@@run" from $p'$.
This is a contradiction, as the equivalence $q\eqSig{x-2}p$ implies $\Lang{\initialAut{\A}{q}}=\Lang{\initialAut{\A}{p'}}$ (since $\eqSig{x-2}$ refines $\eqRes{\A}$).
Therefore, for some $k$ we must have $\safeSig{x}{q_k}\subseteq \safeSig{x}{p'}$ and we can extend the path as wanted using the first case.

We may finally deduce the result of Lemma <ref> from the two previous claims.
First, we read the word $u$ from Claim <ref>, which forces to produce priority $x-1$ from any state in $\classSig{x}{q}$. We now show how to use Claim <ref> to redirect each state, one by one, to the class $\classSig{x}{p}$.

We let $(q_1,m_1),\dots, (q_k,m_k)$ be an enumeration of all states such that there exists $s\in \classSig{x}{q}$ with $s \lrpExistsResolver{\resolv}{u:x-1} (q_i,m_i)$.
We note that, by "$[0,x-2]$-faithfulness", $q_i\eqSig{x-2} q\eqSig{x-2} p$.
We recursively build a sequence of $k$ words, $w_1,\dots,w_k\in \SS^*$ by setting:

\[ (q_i,m_i)\lrpResolverMem{\resolv}{w_1\dots w_{i-1}:\geq x-1} (q_i',m_i') \lrpResolverMem{\resolv}{w_i:\geq x-1} \classSig{x}{p} \;   \tand \;\;  \classSig{x}{p}\lrpAllResolver{\resolv}{w_i: x}\classSig{x}{p}. \]

We can indeed do this by letting $w_i = w_{q_i',m_i'}$ as given by Claim <ref>, as by "$[0,x-2]$-faithfulness" $q_i'\eqSig{x-2}p$.

The word $w_1\dots w_i$ satisfies that, for $j\leq i$,  $(q_j,m_j)\lrpResolverMem{\resolv}{w_1\dots w_{i}:\geq x-1} \classSig{x}{p}$.
We conclude the proof of the lemma by putting $w'=uw_1\dots w_k$.

§.§.§ Re-determinisation

We give the proof of Lemma <ref>, that is, we show that we can obtain an "equivalent@@aut" "deterministic" automaton from $\A$ while preserving all the obtained structure of "total preorders" satisfying the conditions of a "structured signature automaton".

We assume that $\A$ is a "parity automaton" "recognising" $W$ with "nested total preorders" defined up to $\leqSig{x}$ such that:

* it is a "$(x-2)$-structured signature automaton",

* preorder $\leqSig{x-1}$ satisfies properties from Items <ref> and <ref> from the definition of a "structured signature automaton",

* preorder $\leqSig{x}$ satisfies the property from Item <ref> from the definition of a "structured signature automaton",

* it is "deterministic over" transitions with priorities different from $x-1$,

* it is "homogeneous", and

* it is "history-deterministic".

Obtaining a deterministic automaton.

An intuitive idea for the construction of $\A'$ was given in Section <ref>. We formalise it and prove its correctness now.

Automaton $\A'$ is obtained by keeping all the structure of $\A$, except for $(x-1)$-transitions; for each state $q$ and letter $a$ such that some transition $q\re{a:x-1}p$ appears in $\A$, we will redefine this transition as $q\re{a:x-1}p'$ for some $p'\eqSig{x-2}p$ as determined next.

For each $\eqSig{x-1}$-class $\classSig{x-1}{q}$ of $\A$, we pick a state in the class that is maximal for $\leqSig{x}$. We let $\intro*\pickMax(q)$ be that state. That is, for two states $q_1\eqSig{x-1}q_2$:

* $\pickMax(q_1)=\pickMax(q_2)$,

* $\pickMax(q_1)\in \classSig{x-1}{q_1}$, and

* $q_1\leqSig{x} \pickMax(q_1)$.

We recall that we have a total order over the "${<}x$-safe components" of $\A$ given by $\safeComp{x}_1,\safeComp{x}_2,\dots, \safeComp{x}_{k_x}$.
Let $q\in \safeComp{x}_i$ and $a\in \SS$ such that $q\re{a:x-1}p$ appears in $\A$.
If it exists, we let $\intro*\inext$ be the maximal $0\leq i_\mnext<i$ such that there is some $p'\in \classSig{x-2}{p}$, $p'\in \safeComp{x}_{i_\mnext}$. If index $\inext$ is not defined, we let it be the maximal index $i\leq \inext\leq k_x$ with the previous property.
We fix a state $p_{q,a}\in \safeComp{x}_{\inext}$ with $p_{q,a}\in \classSig{x-2}{p}$.
We let the "$a$-transition" from $q$ in $\A'$ be $q\re{a:x-1} \pickMax(p_{q,a})$.
This completes the description of $\A'$. It is indeed "deterministic", as $\A$ is "homogeneous" and "deterministic over" transitions with priorities different from $x-1$.

We can find a maximal state $\pickMax(q)$ for $\leqSig{x}$ in the class $\classSig{x-1}{q}$ in polynomial time, as the comparison of "${<}x$-safe languages" can be done in polynomial time (Lemma <ref>).
Therefore, automaton $\A'$ can be built in polynomial time.

Automaton $\A'$ is a "$\eqSig{x-2}$-nice transformation of $\A$ at level $x-1$".

This is clear, as the restriction of $\A'$ to transitions using a "priority" different from $(x-1)$ coincides with that of $\A$, and every transition $q\re{a:x-1}p'$ in $\A'$ comes from a transition $q\re{a:x-1}p$ in $\A$ with $p\eqSig{x-2}p'$.

For every state $q\in Q$, we have $\Lang{\initialAut{\A'}{q}} = \Lang{\initialAut{\A}{q}}$.
In particular, automaton $\A'$ "recognises" the language $\Lang{\A}$.

For simplicity, we give the proof just for the initial state; the proof being identical for any other state.

Let $w\in \SS^\oo$. If the minimal "priority" produced infinitely often by the "run over $w$" in $\A'$ is $y<x-1$ or $y>x-1$, then $w$ is "accepted by" $\A'$ if and only if $w$ is "accepted by" $\A$, by Lemma <ref> and the fact that $\A'$ is a "$\eqSig{x-2}$-nice transformation of $\A$ at level $x-1$".

Assume that the minimal "priority" produced infinitely often by the "run over $w$" in $\A'$ is $x-1$ (so it is "rejecting@@run"), and suppose by contradiction that $w$ is "accepted by" $\A$. By Lemma <ref>, an "accepting run" over $w$ in $\A$ cannot produce a priority $y<x$ infinitely often. Therefore, it eventually remains in a "${<}x$-safe component" $\safeComp{x}_{i_\A}$. Let $\rr$ be such an "accepting run", and let $\rr'$ be the "run over $w$" in $\A'$. We represent them as:

\[ \rr = q_0 \lrp{u\phantom{..}} q_N\re{w_N:\geq x} q_{N+1} \re{w_{N+1}:\geq x}\dots \;, \quad \rr' = q_0' \lrp{u\phantom{..}} q_N' \lrp{w_N: x_N'} q_{N+1}' \re{w_{N+1}: x_{N+1}'}\dots, \]

where $u$ is the prefix of size $N$ of $w$, $q_0=q_0'=q_\init$, and we suppose that $q_k\in \safeComp{x}_{i_\A}$ for all $k\geq N$.
As $\A'$ is a "$\eqSig{x-2}$-nice transformation at level $x-1$", we have that $q_k\eqSig{x-2} q_k'$ for all $k$.
Let $k_1<k_2<k_3 \dots$ be the positions greater than $N$ where $x_{k_j}'=x-1$, and let $i_1,i_2,\dots$ be the indices of the "${<}x$-safe components" such that $q_{k_j+1}\in \safeComp{x}_{i_j}$, that is, when taking the transition $q_{k_j}\re{w_{k_j}:x-1}$ we land in $\safeComp{x}_{i_j}$.

Eventually, $i_j = i_\A$.

Consider a transition $q_{k_j}' \re{w_{k_j}:x-1} q_{k_j+1}'$, and suppose first that $i_\A< i_{j-1}$.
We claim that $i_\A\leq i_j < i_{j-1}$. This would end the proof, as we obtain a strictly decreasing sequence of indices bounded by $i_\A$.
In order to determine $i_j$, we need to look at the definition of $\inext$.
As $q_k\eqSig{x-2}q_k'$ for all $k$, there are always states in $\classSig{x-2}{q_{k_j+1}'}$ in some "${<}x$-safe components" with an index  $i_\A\leq i < i_{j-1}$.
Thus, we obtain the desired result by definition of $\inext$.

If $i_{j-1}\leq i_\A$, by definition of $\inext$, there is be a sequence of decreasing indices $i_{j-1}>i_j>i_{j+1}>\dots$ until no $\eqSig{x-2}$-equivalent state appears in a strictly smaller safe component.
By the same argument as before, there is always a $\eqSig{x-2}$-equivalent state in $\safeComp{x}_{i_\A}$, so eventually $i_\A\leq i_{j'}$, and either this is an equality, or we reduce to the previous case.

Let $j$ be the first position such that $i_j = i_\A$, and consider transitions $q_{k_j} \re{w_{k_j}:\geq x} q_{k_j+1}$ and $q_{k_j}' \re{w_{k_j}:x-1} q_{k_j+1}'$ in $\rr$ and $\rr'$, respectively.
By definition of "$x-1$-transitions" of $\A'$, the state we go to in $\rr'$ is $q_{k_j+1}'= \pickMax(q_{k_j+1})$.
As we have chosen $\pickMax(q_{k_j+1})$ maximal in its $\eqSig{x-1}$-class, we have $q_{k_j+1}\leqSig{x} q_{k_j+1}'$, so we have the inclusion of "${<}x$-safe languages" between these states.
Therefore, if there is a "${<}x$-safe run" over $w'$ from $q_{k_j+1}$ in $\A$, there is also such a "safe run@@sig" over $w'$ from $q_{k_j+1}'$ in $\A'$.
This contradicts the fact that the run $\rr'$ produces priority $x-1$ infinitely often, while the run $\rr$ is "${<}x$-safe@@run" from $q_{k_j+1}$, concluding the proof.

To finish the proof of Lemma <ref>, we just need to show that $\A'$ preserves all the properties	of the preorders induced by $\A$.
As in the previous section, to obtain "normality" of the automaton and Item <ref>, we rely on a technical lemma that tells us that we can connect states in the same $\eqSig{x-2}$-component as desired.

Let $q\eqRes{x-2}p$ be two different states in $Q$. There is a word $w\in \SS^*$ and a path $q\lrp{w:> x-2} p$ in $\A'$

Let $i_p$ be the index such that $p\in \safeComp{x}_{i_p}$. If $q$ belongs to this same "safe component@@sig", we can connect both states by a path producing priorities $\geq x$.
If not, by "${<}x$-safe centrality" of $\A$, there is a word $w_1\in \safeSig{x}{p}\setminus \safeSig{x}{q}$. We let $q\lrp{w_1:x-1}q_1$ and $p\lrp{w_1:\geq x} p_1$. We have that $q_1\eqSig{x-2} p_1$ and $p_1\in \safeComp{x}_{i_p}$. While $q_j\notin \safeComp{x}_{i_p}$, we extend this run in a similar way.
Using the same argument as in the proof of the previous lemma, by definition of $\inext$ each time that the run from $q$ sees a priority $x-1$ it decreases the index of its "safe component@@sig", so eventually it must land in $\safeComp{x}_{i_p}$.

Let $q\lrp{w:y}p$ be a path in $\A$. There is a path $q\lrp{w':y} p$ in $\A'$ connecting the same states and producing the same minimal priority.

If $y\geq x$ we can just take $w=w'$.
Suppose $y<x$ and consider the run $q\lrp{w:y'}p'$ in $\A'$. By Lemma <ref>, $p\eqSig{x-2}p'$. Also, $y=y'$ (if $y<x-1$, this is given by Lemma <ref>, if $y=x-1$, by the definition of $\A'$).
By the previous lemma, we can extend this run to $p'\lrp{w_2:\geq x-2}p$, and take $w' =ww_2$.

Automaton $\A'$, with the preorders $\leqSig{0},\dots, \leqSig{x}$ inherited from $\A$ satisfies:

* it is a "$(x-2)$-structured signature automaton",

* preorder $\leqSig{x-1}$ satisfies properties from Items <ref> and <ref> from the definition of a "structured signature automaton", and

* preorder $\leqSig{x}$ satisfies the property from Item <ref> and, for priorities $y<x$, also that from Item <ref>.

We start verifying the properties for the preorders $\leqSig{x-1}$ and $\leqSig{x}$.
We note that the "${<}x$-safe components" of $\A'$ exactly correspond to those in $\A$, and that for every $q\in Q$, $\safeSigAut{x}{q}{\A}=\safeSigAut{x}{q}{\A'}$. The fact that $\leqSig{x-1}$ satisfies Items <ref> and <ref>, and that  $\leqSig{x}$ satisfies Item <ref> follows immediately.
We check that relation $\eqSig{x}$ satisfies Item <ref> for priorities $y<x$. For $y\leq x-2$, this follows from the fact that $\eqSig{x}$ refines $\eqSig{x-2}$, and the latter relation satisfies Item <ref>. For $y=x-1$, if $q\re{a:x-1} p$ and $q'\re{a:x-1} p'$, with $q\eqSig{x}q'$, by definition of the "$x-1$-transitions" in $\A'$, $p = \pickMax(p) = \pickMax(p') = p'$.

Checking that $\A'$ is a "$(x-2)$-structured signature automaton" poses no difficulty. It can be done in an analogous way as it was done in the proof of Lemma <ref>; by applying Lemma <ref> to obtain "normality" of $\A'$ and property from Item <ref>.

§.§.§ Uniformity of $x$-transitions over $\eqSig{x}$-classes

We finally show how to transform $\A$ into an "equivalent@@aut" automaton that is either "$x$-structured signature", or strictly smaller. The techniques presented here generalise those applying to Büchi automata appearing  in Section <ref> of the warm-up.

In all this subsection we suppose that $\A$ is "deterministic" "parity automaton" "recognising" $W$ with "nested total preorders" defined up to $\leqSig{x}$ such that:

* it is a "$(x-2)$-structured signature automaton",

* preorder $\leqSig{x-1}$ satisfies properties from Items <ref> and <ref> from the definition of a "structured signature automaton", and

* preorder $\leqSig{x}$ is a "congruence" and satisfies the property from Item <ref> and, for priorities $y<x$, also that from Item <ref> .

Our objective is to prove, under this list of hypothesis, that we can either obtain an "equivalent@@aut" "deterministic" "$x$-structured signature automaton", or reduce the number of states of $\A$.

We remark that $\eqSig{x}$ already satisfies most desired properties of "monotonicity@@cong"; only the "uniformity for" $x$-transitions is missing.

The relation $\eqSig{x}$ is a "$[0,x-1]$-faithful congruence". Moreover, over each $\eqSig{x-1}$-class, transitions using priorities ${\geq}x$ are "monotone for" $\leqSig{x}$.

The "$[0,x-2]$-faithfulness" follows from the fact that $\eqSig{x}$ refines $\eqSig{x-2}$ and $\A$ is "$(x-2)$-structured signature".
The "uniformity@@cong" of $(x-1)$-transitions over $\eqSig{x}$-classes is given by the fact that $\eqSig{x}$-equivalent states have the same "${<}x$-safe language", combined with the "uniformity@@cong" of ${<}(x-1)$-transitions.

The fact that $\eqSig{x}$ is a "congruence for" "$(x-1)$-transitions" follows from Item <ref> of the definition of a "structured signature automaton" (we recall that $\eqSig{x}$ satisfies this property by hypothesis).
The "congruence for" ${\geq}x$-transitions and the monotonicity of ${\geq}x$-transitions for $\leqSig{x}$ at each $\eqSig{x-1}$-class follow from the monotonicity of "${<}x$-safe languages" (Lemma <ref>).

Polished automata.
We generalise the notion of "polished automata@@buchi" from Section <ref> to our current setting.

We say that the class $\classSig{x}{q}$ is ""$x$-polished@@class"" if:

* Words producing priority $x$ "act uniformly" in $\classSig{x}{q}$. That is, if $q_1,q_2\in \classSig{x}{q}$ and $q_1\lrp{w:x}$, then $q_2\lrp{w:x}$.

* For every $q_1,q_2\in \classSig{x}{q}$, $q_1\neq q_2$, there is a path $q_1\lrp{w:>x}q_2$ producing exclusively priorities $>x$ joining $q_1$ and $q_2$.

We say that the automaton $\A$ is ""$x$-polished@@aut"" if all its $\eqSig{x}$-classes are "$x$-polished@@class".

We remark that, as $x\geq 2$ and we assume that the automaton $\A$ is in "normal form", all non-trivial $\eqSig{x}$-classes are "recurrent@@class": if a $\eqSig{x}$-class is not trivial, there is a cycle visiting all the states of the class.
Therefore, we do not need to take care of "transient classes" (as it was the case in Lemma <ref> from the warm-up).

We can decide whether $\A$ is "$x$-polished@@aut" in polynomial time.

As $\eqSig{x}$ is a "$[0,x-1]$-faithful congruence" (Lemma <ref>), we just need to check the first property for letters, which can be done in linear time in $|\Sigma||\A|$.

For the second property, we just need to check whether, for each $q\in Q$, the "subautomaton" induced by $\classSig{x}{q}$ and transitions with priority ${>}x$ is strongly connected.

*Case 1: $\A$ is already $x$-polished Assume that $\A$ is "$x$-polished@@aut". In this case, it is almost an "$x$-structured signature automaton". We just need to ensure that if $q\eqSig{x} q'$, two transitions $q\re{a:x}p$ and $q'\re{a:x}p'$ go to a same state $p=p'$.

We remark that $\eqSig{x}$ already satisfies most desired properties of "monotonicity@@cong"; only the "uniformity for" $x$-transitions is missing.

In order to obtain the "strong congruence" of $x$-transitions (Item <ref>), we redirect some $x$-transitions of $\A$.
For each $\eqSig{x}$-class $\classSig{x}{q}$, pick an arbitrary state $\pickP(q)\in \classSig{x}{q}$. (Formally, $\intro*\pickP\colon Q \to Q$ such that $\pickP(q)=\pickP(q')$ if $q\eqSig{x}q'$). We let $\A'$ be the automaton obtained as follows:

* The states of $\A'$ are the same than those in $\A$.

* Transitions using priorities different from $x$ are those in $\A$.

* If $q\re{a:x}p$, we let $q\re{a:x}\pickP(p)$ in $\A'$.

It is immediate to check that $\A'$ is a "$\eqSig{x}$-nice transformation of $\A$ at level $x$". Moreover, $\autGeq{\A}{x+1} = \autGeq{\A'}{x+1}$. These remarks directly give:

$\A'$ is "$x$-polished@@aut".

There is a path $q\lrp{w:y}p$ in $\A$ if and only if there is a path $q\lrp{w':y}p$ in $\A'$.

We suppose that there is $q\lrp{w:y}p$ in $\A$ (the converse proof is symmetric).
If $y>x$, we have that $q\lrp{w:y}p$, as $\autGeq{\A}{x+1} = \autGeq{\A'}{x+1}$.
If $y\leq x$, as $\A'$ is a "nice transformation at level $x$", we have that $q\lrp{w:y}p'$ in $\A'$, with $p\eqSig{x}p'$. As $\A'$ is "$x$-polished@@aut", there is a path $p'\lrp{w_2:>x} p$. We conclude by taking $w'=ww_2$.

Automaton $\A'$ is "equivalent to@@aut" $\A$, and it is an "$x$-structured signature automaton".

The fact that $\Lang{\A} = \Lang{\A'}$ follows easily using that $\A'$ is a "$\eqSig{x}$-nice transformation of $\A$ at level $x$" and applying Lemma <ref>.
Lemma <ref> implies that $\A'$ is in "normal form".
Verifying that $\A'$ is an "$x$-structured signature automaton" is just a routine check, using that $\A'$ is "$x$-polished@@aut" and Lemma <ref>.

*Case 2: Polishing a class

Assume now that there is a class $\classSig{x}{q}$ that is not "$x$-polished@@class" in $\A$. We show that we can remove some states from this class, obtaining an strictly smaller "equivalent@@aut" automaton.

Local languages and local automata.

We define the ""$x$-local alphabet at $\classSig{x}{q}$"" by

\[
\intro*\locAlph{x}{q} = \{w\in \SS^+ \mid \classSig{x}{q} \lrp{w:\geq x} \classSig{x}{q} \text{ and for any proper prefix } w' \text{ of } w,  \classSig{x}{q} \lrp{w:\geq x} \classSig{x}{p}\neq \classSig{x}{q} \}.
\]

We remark that, as $\eqSig{x}$ is a "congruence for" "${\geq}x$-transitions" (Lemma <ref>),  $\locAlph{x}{q}$ is well-defined and the notation $\classSig{x}{q} \lrp{w:\geq x}$ can be used. A word $w\in \SS^*$ belongs to $\locAlph{x}{q}^*$ if and only if it connects states in the class $\classSig{x}{q}$. Elements in $\locAlph{x}{q}$ are those that do not pass twice through this class.
Note that $\locAlph{x}{q}$ is a "prefix code", and therefore it is a "proper alphabet" (even if, in general, it is infinite).

Seeing words in $\locAlph{x}{q}^\omega$ as words in $\SS^\omega$, define the ""localisation of $W$ to $\classSig{x}{q}$"" to be the objective

\[
\intro*\locLang x q = \{ w \in \locAlph{x}{q}^\omega \mid w \in \Lang{\initialAut{\A}{q}}\}.
\]

Observe that, as $\eqSig{x}$ "refines" $\eqRes{\A}$, this last definition does not depend on the choice of $q$ and $\locLang x q$ is "prefix-independent".
Moreover, $\locLang x q$ is "half-positional" over finite, "$\ee$-free" "Eve-games": any "$\locLang x q$-game" in which "Eve" could not "play optimally using positional strategies" would provide a counterexample for the "half-positionality" of $\Lang{\initialAut{\A}{q}}$, which is "half-positional" if $W$ is (Lemma <ref>).

The ""local automaton of the class $\classSig{x}{q}$"" is the automaton $\intro*\localAutSig{x}{q}$ defined as:

* The set of states is $\classSig{x}{q}$.

* The initial state is arbitrary.

* For $w\in \locAlph{x}{q}$, $q_1\re{w:y}q_2$ if $q_1\lrp{w:y}q_2$ in $\A$ (we must have $y\geq x$).

Super words and super letters for local languages.

We recall some terminology introduced in the warm-up. Assume that $L$ is a "prefix-independent" language.
We say that $u\in \SS^+$ is a ""super word"" for $L$ if, for every $w\in \SS^\oo$, if $w$ contains $u$ infinitely often as a factor, then $w\in L$.
If $s$ is a letter, we say that it is a ""super letter"".

For $q$ a state and $x$ an even priority, we let $\intro*\BLetters{x}{q}\subseteq \locAlph{x}{q}$ be the set of "super letters for" $\locLang{x}{q}$, and we write $\intro*\NLetters{x}{q} = \locAlph{x}{q}\setminus \BLetters{x}{q}$. We refer to $\NLetters{x}{q}$ as the set of ""neutral letters@@sig"" of $\locAlph{x}{q}$ (for $\locLang{x}{q}$).

A word $w\in \locAlph{x}{q}^\oo$ is a "super word" for $\locLang x q$ if and only if $w$ "produces priority $x$ uniformly" in $\classSig{x}{q}$, that is, for all $q'\in \classSig{x}{q}$,  $q'\lrp{w:x}\classSig{x}{q}$.

By "normality" of $\A$, if there is $q_1\in[q]$ such that $q_1\lrp{w:>x}q_2$, there is a word $w'\in \SS^*$ labelling a returning path $q_2\lrp{w':x+1}q_1$. Therefore, $(ww')^\oo\notin \Lang{\initialAut{\A}{q}}$, so $w$ is not a "super word" for $\locLang x q$.
The converse implication is clear, since each time word $w$ is read, the minimal priority produced by the automaton is $x$.

In particular, using previous lemma, we can detect the set of "super letters" $\BLetters{x}{q}$ in polynomial time.

Super words of positional languages.

The use of the  hypothesis of "half-positionality" of $W$ for proving Lemma <ref> resides in the next fundamental result.

Let $w\in \locAlph{x}{q}^+$ be a "super word" for $\locLang{x}{q}$. Then, $w$ contains some "super letter".

If $w$ is already a letter in $\locAlph{x}{q}$, we are done. If not, let $w=w_1w_2$ be any non-trivial decomposition into smaller words $w_1,w_2\in \locAlph{x}{q}^+$. We show that either $w_1$ or $w_2$ are "super words" for $\locLang{x}{q}$. This allows us to finish the proof, as we can recursively chop $w$ into strictly smaller "super words" until obtaining a "super letter".

Suppose by contradiction that neither $w_1$ or $w_2$ are "super words". Then, by Lemma <ref>, there are states $q_1$ and $q_2$ such that $q_1\lrp{w_1:>x}q_1'$ and $q_2\lrp{w_2:>x}q_2'$.
By "normality", we obtain returning paths $q_1'\lrp{u_1:x+1}q_1$ and $q_2'\lrp{u_2:x+1}q_2$.
Therefore, $(w_1u_1)^\oo\notin W$ and $(w_2u_2)^\oo\notin W$.
We consider the "game" $\G$ with "winning condition" $\Lang{\initialAut{\A}{q}}$ consisting in a vertex $v$ with self loops $u_1w_1$ and $u_2w_2$ (see Figure <ref> from the warm-up).
"Eve" can  "win" game $\G$, as alternating the two self loops she produces the word $(u_1w_1w_2u_2)^\oo$, which belongs to $\Lang{\initialAut{\A}{q}}$ since $w_1w_2$ is a "super word".
However, "positional strategies" in this game produce either $(w_1u_1)^\oo$ or $(w_2u_2)^\oo$, both losing.
This contradicts the "half-positionality" of $\Lang{\initialAut{\A}{q}}$, and therefore, that of $W$ (Lemma <ref>).

Polishing a $\eqSig{x}$-class of $\A$.

We show how to "polish" the class $\classSig{x}{q}$ of $\A$. This process has the property that, either $\classSig{x}{q}$ is already "polished@@classSig", or the obtained automaton $\A'$ has strictly less states than $\A$, as desired.

Assume that the class $\classSig{x}{q}$ is not "$x$-polished".
Consider the restriction of $\localAutSig{x}{q}$ to transitions labelled with $\NLetters{x}{q}$, which we denote $\localAutSig{x}{q}'$. Take $S_{\classSig{x}{q}}$ to be a ""final SCC"" of $\localAutSig{x}{q}'$ (that is, one without edges leading to states not on itself).

Fix a state $q_0\in \classSig{x}{q}$.
Consider the automaton $\A'$ obtained from $\A$ by removing states in $\classSig{x}{q} \setminus S_{\classSig{x}{q}}$, and redirecting transition that go to $\classSig{x}{q} \setminus S_{\classSig{x}{q}}$ in $\A$ to transitions towards $q_0$.
For these redirected transitions, we keep the same priority if it is $\leq x$, and set it to $x$ otherwise. Formally:

* The set of states of $\A'$ is $Q' = Q \setminus \left( \classSig{x}{q} \setminus S_{\classSig{x}{q}} \right)$.

* The initial state is $q_\init$, or $q_0$ if $q_\init\in \classSig{x}{q} \setminus S_{\classSig{x}{q}}$.

For $q'\in Q'$:

* If $q'\re{a:y}p$ in $\A$ and $p\notin \classSig{x}{q}$, then $q\re{a:y}p$ in $\A'$.

* If $q'\re{a:y}p$ in $\A$,  $p\in \classSig{x}{q}\setminus S_{\classSig{x}{q}}$, and $y\leq x$, then $q'\re{a:y}q_0$ in $\A'$.

* If $q'\re{a:y}p$ in $\A$,  $p\in \classSig{x}{q} \setminus S_{\classSig{x}{q}}$, and $y> x$, then $q'\re{a:x}q_0$ in $\A'$.

For transitions in the two latter cases, we say that $q'\re{a:y}q_0$ has been ""redirected@@polish"" from $q'\re{a:y}p$.

If $\classSig{x}{q} = S_{\classSig{x}{q}}$, then $\A' = \A$.

The following lemma will be use to show that we can compute $\A'$ in polynomial time, to prove the correctness of $\A'$, and to obtain that $\classSig{x}{q}$ is "$x$-polished@@class" in $\A'$.

Let $q_1,q_2\in S_{\classSig{x}{q}}$, and let $w\in \NLetters{x}{q}^*$ labelling a path $q_1\lrp{w:y}q_2$ in $\A$.
Then, $y>x$.

The fact that $y\geq x$ simply follows from the fact that $\NLetters{x}{q}\subseteq \locAlph{x}{q}$, which, by definition, contains words connecting the states in $\classSig{x}{q}$ producing no priority ${<}x$.

Suppose by contradiction that $y=x$. Then, by the same argument as in the proof of Lemma <ref> (see also Claim <ref>),
there is $w'\in \NLetters{x}{q}^*$ "producing priority $x$ uniformly" in $\classSig{x}{q}$ and coming back to this class; that is, for every $q'\in \classSig{x}{q}$, $q'\lrp{w':x}\classSig{x}{q}$.
Therefore, by Lemma <ref>, $w'$ is a "super word".
By Lemma <ref>, $w'$ must contain a "super letter", a contradiction, as $w'\in \NLetters{x}{q}^*$ and $\locAlph{x}{q}$ is a "proper alphabet".

Automaton $\A'$ can be computed in polynomial time from $\A$.

To obtain $S_{\classSig{x}{q}}$, we first build a finite representation of the restriction of $\localAutSig{x}{q}$ to "neutral letters@@polishSig" (we recall that, in general, $\localAutSig{x}{q}$ might have an infinite number of transitions).
One way of doing that is to build the following graph $G$: for each pair of states $q_1,q_2\in \classSig{x}{q}$ and each $y> x$, we put an edge $q_1\re{y} q_2$ if there is a path from $q_1$ to $q_2$ producing $y$ as minimal priority and not passing trough another state in $\classSig{x}{q}$.
By Lemma <ref>, $S_{\classSig{x}{q}}$ is a subgraph of $G$. To obtain the states in $S_{\classSig{x}{q}}$ we just need to perform a decomposition in "SCCs" of $G$ and take a "final SCC" of it.
If $W$ is not "half-positional", the procedure described here does provide a set of states $S_{\classSig{x}{q}}$, but it might lead to an incorrect automaton $\A'$. If our objective is to decide the "half-positionality" of $W$, at the end of the procedure we need to check the equality $\Lang{\A} = \Lang{\A'}$; if it does not hold, we can conclude that $W$ is not "half-positional".

We consider $\A'$ equipped with the preorders $\leqSig{0},\dots,\leqSig{x}$ inherited from $\A$.

Automaton $\A'$ is a "$\eqSig{x}$-nice transformation of $\A$ at level $x$".

We first note that, by Lemma <ref>, $\eqSig{x}$ is "$[0,x-1]$-faithful" in $\A$, so it makes sense to speak of a "$\eqSig{x}$-nice transformation at level $x$".

Automaton $\autGeq{\A'}{x+1}$ coincides with the "subautomaton" of $\autGeq{\A}{x+1}$ induced by states in $Q'$.
Indeed, let $q_1',q_2'\in Q'$ and $q_1'\re{a:>x}q_2'$ in $\A$. As these states are in $Q'$, $q_2'\notin \classSig{x}{q} \setminus S_{\classSig{x}{q}}$, so the transition has not been "redirected@@polish", and it appears in $\A'$. Conversely, all transitions producing a priority $>x$ in $\A'$ appear in $\A$.

We show that $\eqSig{x}$ is "$[0,x-1]$-faithful" in $\A'$ and $\autLeq{\A}{x-1}{x-1}=\autLeq{\A}{x-1}{x-1}$.
Let $p_1,p_2\in Q'$ such that $p_1\eqSig{x}p_2$, and let  $p_1\re{a:y_1'}q_1'$ and $p_2\re{a:y_2'}q_2'$ be two transitions in $\A'$.
Transitions that have not been "redirected@@polish" satisfy the congruence requirements, as they satisfy them in $\A$.
Assume that the first of these transitions have been redirected from  $p_1\re{a:y_1}q_1$ in $\A$. We have that $q_1'=q_0\eqSig{x} q_1$, so, $q_1'\eqSig{x}q_2'$ by the congruence property in $\A$.
If $y_1'<x$, then $y_1=y_1'$ and the "$y_1$-uniformity" of transitions in $\A$ yields $y_1'=y_2'$.
Therefore, we also have that $y_1'\geq x$ if and only if $y_2'\geq x$
This gives both  the "$[0,x-1]$-faithfulness" in $\A'$ and the equality of the "quotient@@leq" automata.

As $\eqSig{x}$ "refines" $\eqRes{\A}$, the latter relation is also a "congruence" in $\A'$ and $\quotAut{\A}{\A} = \quotAut{\A'}{\A}$.

Automaton $\A'$ "recognises" $\Lang{\A}$

Let $w\in \SS^\oo$. If $w$ is "accepted@@byPriority" or "rejected with a priority" $y<x$ or $y>x$ in $\A'$, by Lemma <ref>, $w\in \Lang{\A}$ if and only if $w\in \Lang{\A'}$.
Suppose then that $w$ is  "accepted with priority" $x$ in $\A'$. Let $\rr'$ be the "run over" $w$ in $\A'$. If $\rr'$ eventually does not take any "redirected transition@@polish", then it is eventually a run in $\A$, and we can conclude by Lemma <ref>. Suppose that $\rr'$ takes "redirected transitions@@polish" infinitely often; moreover, eventually all such transitions produce priority $x$. We decompose $\rr'$ as follows:

\[ \rr' = q_\init \lrp{w_0} p_0'\re{a_0:x} q_0 \lrp{w_1:\geq x} p_1'\re{a_1:x} q_0 \lrp{w_1:\geq x} p_2'\re{a_2:x} q_0 \lrpE{} \dots ,\]

where no priority $<x$ appears after $p_0'$, each  transition $p_i'\re{a_1:x} q_0$ is a "redirected@@polish" one, and no "redirected@@polish" transition appears in  paths $q_0 \lrp{w_i:\geq x}$, in particular, these paths appear in $\A$.

For each $i\geq 1$, the word $w_ia_i$ belongs to $\locAlph{x}{q}^+$ and is a "super word for" $\locLang{x}{q}$.

The word $w_ia_i$ connects two states in $\classSig{x}{q}$ in $\A'$ producing no priority $<x$. Since $\A'$ is a "$\eqSig{x}$-nice transformation at level $x$",
word  $w_ia_i$ also connects states in $\classSig{x}{q}$ in $\A$, without producing priorities $<x$. Therefore, it belongs to $\locAlph{x}{q}^+$.

Consider the path $q_0\lrp{w_i}p_i'\re{a_i}q'$ in $\A$.
As we suppose that transition $p_i'\re{a_i}q_0$ has been "redirected@@polish" in $\A'$, $q'\notin S_{\classSig{x}{q}}$. Then, since $S_{\classSig{x}{q}}$ is a "final SCC" of the restriction of $\localAutSig{x}{q}$ to "$\NLetters{x}{q}$-transitions@@in", $w_ia_i$ contains some factor that is a letter in $\locAlph{x}{q}\setminus\NLetters{x}{q}$. Such a factor is a "super letter", so $w_ia_i$ is a "super word".

Consider the "run over" $w$ in $\A$, that we divide following the decomposition of $\rr'$:

\[ \rr = q_\init \lrp{w_0} p_0\re{a_0:\geq x} q_1 \lrp{w_1:\geq x} p_1\re{a_1:\geq x} q_2 \lrp{w_2:\geq x} p_2\re{a_2:\geq x} q_3 \lrpE{} \dots .\]

As $\A'$ is a "$\eqSig{x}$-nice transformation at level $x$", $q_i\eqSig{x}q_0$ for all $i$, and $\rr$ does not produce any priority $<x$ from $p_0$.
By Lemma <ref>, as $w_ia_i$ is a "super word", the path $q_i\lrp{w_ia_i} q_{i+1}$ produces priority $x$.
Therefore, $w$ is "accepted by@@aut" $\A$.

The class $\classSig{x}{q}$ is "$x$-polished@@class" in $\A'$.

Let $q_1,q_2\in Q'$ be two states in the class $\classSig{x}{q}$. Assume that, for a word $w\in \SS^*$, the path $q_1\lrp{w:x}p_1$ produces priority $x$. As $\eqSig{x}$ is "$[0,x-1]$-faithful", $q_2\lrp{w:\geq x}p_2$. Suppose by contradiction that this latter path produces exclusively priorities $>x$. Then, this path also exists in $\A$, and by "normality" (of $\A$), there is a returning path $p_2\lrp{w':x+1}q_2$.
We obtain therefore a path $q_1\lrp{ww':x}\classSig{x}{q}$. However, in $\A'$, $\classSig{x}{q} = S_{\classSig{x}{q}}$, so, by Lemma <ref>, $ww'$ contains a "super letter", so $(ww')^\oo\in \Lang{\initialAut{\A}{q}}$, contradicting the fact that there is a cycle $q_2\lrp{ww':x+1} q_2$.

The second property of the definition of an "$x$-polished class" is satisfied in $\A'$, as we have "redirected@@polish" all "$x$-transitions" entering in $\classSig{x}{q}$ to the state $q_0$.

We show the third item. Let $q_1,q_2\in \classSig{x}{q}$. Since  $\classSig{x}{q} = S_{\classSig{x}{q}}$ in $\A'$, there is a path $q_1\lrp{w\phantom{.}} q_2$  for some $w\in \NLetters{x}{q}^*$. By Lemma <ref>, this path produces exclusively priorities ${>}x$.

This lemma allows us to conclude. We have obtained a deterministic automaton $\A'$ that is "equivalent@@aut" to $\A$. We claim that $\sizeAut{\A'}<\sizeAut{\A}$.
Indeed, if this was not the case, we would have that $\classSig{x}{q} = S_{\classSig{x}{q}}$, so, by Remark <ref>, $\A= \A'$. By the previous Lemma <ref> this implies that $\classSig{x}{q}$ was already "$x$-polished@@class" in $\A$, a contradiction.

Discussion: Why not just continue polishing?
We have just showed a method to "$x$-polish@@class" a given class of $\A$. The natural continuation would be to "polish@@sig" the rest of classes, until obtaining an "$x$-polished automaton", and then apply the first case.
The main difficulty is that the polishing operation we have presented might break the "normality" of $\A$. "Normality" of automata is key in all the process
(see for example Lemma <ref>), so we cannot guarantee to be able to continue polishing the classes of $\A'$.
We would need to be able to either show that $\A'$ is in "normal form" (for example, by having an analogous to Lemma <ref>), or to show that we can "normalise" $\A'$ while maintaining the properties of being an "$(x-2)$-structured signature automaton".
We have not succeeded in ensuring these properties, although we believe that it should be possible to do so.