=Paper=
{{Paper
|id=Vol-2864/paper16
|storemode=property
|title=Formal Models of Question-Answering Machine
|pdfUrl=https://ceur-ws.org/Vol-2864/paper16.pdf
|volume=Vol-2864
|authors=Igor Chimir,Anatolii Verlan
|dblpUrl=https://dblp.org/rec/conf/cmis/ChimirV21
}}
==Formal Models of Question-Answering Machine==
https://ceur-ws.org/Vol-2864/paper16.pdf
Formal Models of Question‐Answering Machine
Igor A. Chimira, and Anatolii F. Verlanb
a
Odessa State Environmental University, 15 Lvovskaya St., 65016, Odessa, Ukraine
b
The Georgy Puchov Institute for Energy Modeling. National Academy of Science, 15 General Naumov St.,
03164, Kiev, Ukraine
Abstract
The article describes two models of question-answering dialogue machine: (1) model based
on the idea of Mealy finite automata, and (2) model based on the idea of Petri net. Both mod-
els are problem-independent and describe question-answering dialogue process, which is in-
dependent of the subject area of the dialogue. The problem independence of the models is a
consequence of a unified cognitive cycle of dialogue used in them. The unified cognitive cy-
cle of dialogue is similar to Neisser's cyclical model of perception. Models are designed to
specify a "dialogue machine" that simulates a goal-oriented behavior of the active dialogue
agent when solving a problem by means of a question-answering dialogue. Implementation
of the models presupposes data-driven approach when main components of the "dialogue
machine" are not map in the program code but represented by data stored in the database.
Keywords 1
Question-answering dialogue, Dialogue agent, Dialogue script, Cognitive cycle of dialogue.
1. Introduction
Dialogue communication is one of the phenomena of human mental activity and is a subject of
study in such sciences as artificial intelligence, cognitive psychology, erotetic logic and epistemology.
The Turing intelligence test is based on a dialogue process between a human and a technical sys-
tem [1]. Modern presentation of artificial intelligence is based on the concept of intelligent agents [2].
Dialogue communication between the environment and the intelligent agent determine the behavior of
the latter.
In cognitive psychology, one can find theories and models that contribute to understanding the es-
sence of dialogue. Neisser's model of perception is a model of the dialogue process if the source of the
flow of sensory events is one of the dialogue partners [3].
The vehicle for the exchange of knowledge between dialogue partners is a question-answering
pair, therefore erotetic logic provides an apparatus for modeling the logical structure of a dialogue [4].
Epistemology is related to understanding the essence of the dialogue process, since it studies those
types of knowledge that circulate within the question-answer pair. Dialogue plays a key role in So-
cratic epistemology [5].
Question-answering dialogue is one of the types of dialogue that can be operated by artificial dia-
logue agents. In a question-answering dialogue, the information messages of the active agent repre-
sent questions, and the information messages of the reactive agent represent the answers to these
questions. The concepts of “question” and “answer” should be understood not in the narrow, linguistic
sense of the word, but in the broad, behavioral sense. The question is, in the general case, the inter-
rogative stimulus of the active agent, and the answer is the reaction of the reactive agent.
A feature of the question-answering dialogue is its ability to serve as a means of solving a number
of ill-formalized problems. Newell was the first to draw attention to the need to develop methods for
CMIS-2021: The Fourth International Workshop on Computer Modeling and Intelligent Systems, April 27, 2021, Zaporizhzhia, Ukraine
EMAIL: chimir@gmail.com (I. Chimir); a.f.verlan@gmail.com (A. Verlan)
ORCID: 0000-0001-5326-768X (I. Chimir); 0000-0002-8565-2037 (A. Verlan)
© 2020 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
solving ill-formalized problems [6]. Newell believed that ill-formalized problems are those that had
one or more of the following characteristics: problems cannot be specified numerically; goals cannot
be expressed in terms of well-defined objective functions; there is no algorithmic solution to the prob-
lem; an algorithmic solution exists, but it cannot be used due to limited computer resources. In applied
systems of artificial intelligence, there are systems oriented on solving ill-formalized problems. One
of the most extensive classes of such systems is intelligent tutoring systems [7]. The problem of
teaching and knowledge transfer is ill-formalized and can be solved by dialogue methods.
The pragmatic dimension in the modeling of question-answering dialogue processes is aimed at
designing systems focused on solving ill-formalized problems and systems called "chatbots" [8].
In the field of theory and practice of dialogue processes, focused on solving ill-formalized prob-
lems, an important question is how to create, store and repeatedly reproduce dialogue methods. In a
goal-oriented dialogue process, in which the solution of an ill-formalized problem is carried out, the
active agent plays a key role, since it is the active agent who is the carrier of the method for solving
the problem. The article is devoted to the synthesis and description of cognitive and formal problem-
independent dialogue models that can generate protocols of goal-oriented question-answering dia-
logues. Formal models have applied value and can be used as a basis for the development of artificial
dialogue agents.
2. Cognitive cycle of question‐answering dialogue
When developing a dialogue model, it is important that the model is adequate to the processes of
perception and processing of information by a human. In the case when the basis of the formal model
of dialogue is an adequate psychological model, then we can expect that the artificial dialogue agent
inherits the anthropomorphic properties of the system of perception of a human.
Among the theories and models proposed by cognitive psychology and related to the dialogue
process, let us dwell on the models that describe dialogue at the level of perception, which does not
depend on the subject area of the dialogue and on the nature of the problem, which is solved in the
dialogue process. In this sense, a psychological model of dialogue, useful in an applied aspect, should
describe some unified cognitive "dialogue machine".
The dialogue process is similar to the process of perceptual human interaction with the environ-
ment, modeled by the Neisser cycle [3]. The difference lies in the fact that in the process of dialogue,
the main components of the human sensory system - sight and hearing - are connected not to the "nat-
ural" environment, but to the "artificial" environment formed by streams of visual and sound sensory
events generated by the opposite agent of the dialogue. Thus, in the dialogue process, the real envi-
ronment is replaced by an artificial one. However, it is obvious that the perception and subsequent
processing of both sensory events generated by the artificial environment (dialogue agent) and sen-
sory events generated by the natural environment are carried out according to the same "rules and
laws". A diagram illustrating the cognitive cycle of a question-answering dialogue is shown in Figure
1.
The cognitive cycle of the dialogue process, shown in Figure 1, simulates the behavior of an active
agent in a dialogue with fixed roles. Fixing agent roles means prohibiting changing agent roles during
a conversation. One of the agents always asks questions, and the other always answers them. For con-
venience, we will assume that the dialogue cycle begins from the moment when the active agent oper-
ates with a relatively small set of answers, called the set of expected answers, and the real answer of
the reactive agent coincides with one of the answers from the set of expected answers of the active
agent. Thus, one of the main cognitive structures that the active agent operates is the schema-answer,
or mental representation of the answer. The set of expected answers is embedded in a broader cogni-
tive framework called the active agent script. It is assumed that the script of the active agent includes
all the schema-answers necessary for the given dialogue, and that the set of expected answers is some
subset of answers from the script that is relevant to the current cycle of the dialogue process. After the
perception and recognition of the real answer received from the reactive agent, the current set of ex-
pected answers is modified, the purpose of which is to prepare the set of expected answers for the
next cycle. As a result of the modification, a new set of expected answers is formed, including the
answer expected on the next cycle. During the modification process, the current set of expected an-
swers can be replaced in whole or in part.
REACTIVE AGENT ACTIVE AGENT
Active agent script
Hypothesis
Que testing. Hypothesis in the
Transfer of form of question
question
Reactive Forming of
agent Forming
answer interrogative
knowledge hypothesis
Ans Modification of
the set of Set of expected
expected answers
answers
Active agent script
Figure 1: Cognitive cycle of a question‐answering dialogue process
The concept of a dialogue script means that the active agent does not generate new question using
some "super-algorithm", but searches for it in the memory of questions, using the method of achiev-
ing the goal of the dialogue as a method of accessing the memory of questions. Thus, the method of
accessing the memory of questions is a repository of the method for achieving the goal of a dialogue,
or a dialogue method for solving a problem. The concepts "memory of questions" and "dialogue me-
thod of solving a problem" are included in the scope of the concept of "script" of an active agent and
detail its structure.
Introspection and analysis of real protocols of question-answering dialogue processes reveals that
there is an ambiguous relationship between the current answer of the reactive agent and the subse-
quent question generated by the active agent. In other words, in different dialogue transactions for the
same answer received from the reactive agent, the active agent can generate different questions.
Therefore, when developing dialogue methods for solving problems, for modeling the noted ambigu-
ity, it is necessary to take into account the following three principles.
The principle of "depth of dialogue". The principle of "depth of dialogue" means that the active
agent, when forming the next question, must take into account both the perceived answer and the in-
dex of the dialogue cycle. Here, the term "index" is used synonymously with the term name, or identi-
fier. In different dialogue cycles, different questions can be generated for the same answer received
from the reactive agent.
The principle of "history of answers". The principle of "history of answers" means that the active
agent, when forming the next question, must take into account both the perceived answer and the his-
tory of the received answers. In the same dialogue cycle, different questions can be generated for the
same answer received from the reactive agent, depending on what answers were received in the previ-
ous cycles.
The principle of "history of questions". The principle of “history of questions” means that the ac-
tive agent, when forming the next question, must take into account both the perceived answer and the
history of previously formed questions. In the same dialogue cycle, different questions can be formed
for the same answer, depending on what questions were formed in the previous cycles.
The dialogue cycle shown in Fig. 1 describes well the “harmonious dialogue” corresponding to the
Neisser cycle for the case of routine perception. By harmonious dialogue we mean such a dialogue
when both agents are satisfied with their roles and do not want to change them. However, a harmoni-
ous dialogue is not always possible. The initiator of the role change is usually the reactive agent, and
the sign of the moment of the role change is the generation and transmission to the active agent of an
information message with the status of a question. Therefore, one of the ways to take into account the
possibility of changing roles can be to include a question detector in the list of expected answers. A
question detector can be included in each set of expected answers (then agents will be able to change
roles in any dialog cycle) or only in some sets of expected answers (then the roles of agents can be
changed only in some predefined dialogue cycles).
Considered, further, formal problem-independent models of dialogue are models of the dialogue
method of accessing the memory of questions, considered also as a dialogue method for solving a
problem. These models model the behavior of an active agent of a question-answering dialogue, as
the functioning of some "dialogue machine". The purpose of modeling is to identify the components
of the "dialogue machine" that is invariant to the problem being solved and to the subject area of the
dialogue process.
3. Finite‐automaton model
The finite-automaton model of question-answering dialogue simulates a harmonious dialogue and
is based on three assumptions: (1) the problem solved during the question-answering dialogue can be
solved in a finite number of dialogue cycles (dialogue steps); (2) by the beginning of solving the prob-
lem, all questions and answers necessary for the formation of dialogue steps are determined; (3) modi-
fication of the current set of expected answers always generates a new set that is different from the
current one and has a unique index.
The finite-automaton model is a variant of the Mealy automaton [9] and is described by the fol-
lowing formula
DiAM = (QUE, ANS, S, φ) (1)
where DiAM denotes a dialogue access method to the memory of questions.
QUE = {Quei}; i = 1,…,k (2)
QUE – a set of indexes of questions used to solve a problem.
ANS = {Ansi}; i = 1,…,l (3)
ANS – a set of answers used to solve a problem.
S = {Si}; i = 1,…,m (4)
S – a set of states of waiting for an answer. The number of elements of the set S is equal to the total
number of dialogue steps.
φ : S Χ ANS → S Χ QUE (5)
φ – step function that determines the index of the new question and the index of the next step, depend-
ing on the current answer and the index of the current step.
When performing a step, an automaton that simulates a question-answering dialogue process per-
forms iterations consisting of the following sequence of actions: (1) perceived the current answer of
the reactive agent; (2) the current answer of the reactive agent is recognized; (3) the index of the next
question of the active agent is determined.
If the set of answers ANS is not structured in any way, this means that in order to recognize the cur-
rent answer of the reactive agent, the dialog access method must, at each step, operate with the entire
set of answers ANS. For large scripts, the cardinality of this set can be significant. In order to reduce
the cardinality of the set of answers that DiAM operates with at each step, and to make the model prac-
tically realizable, we introduce into the model a set of answers recognizable at the i-th step. The set of
recognizable answers contains only those answers that are expected at the i-th step, are necessary for
the implementation of the dialogue method and, therefore, must be recognized. All other answers will
be referred to the class of answers that are not recognizable at the i-th step. We will use the following
notation: Ri – is the set of answers recognizable at the i-th step; NRi – is the set of answers not recog-
nizable at the i-th step.
The set of answers that are not recognizable at the i-th step includes all answers belonging to the
set ANS and not belonging to the set Ri, i.e.
i i
NR = ANS - R (6)
However, the set of answers that are not recognizable at the i-th step must be considered wider and
understood as the set of any conceivable answers of a reactive agent that do not belong to the set Ri,
i.e.
i i
NR = U - R (7)
where U – is the set of any responses that the reactive dialogue agent can ever generate.
It is natural to assume that the appearance at the i-th step of any answer belonging to NRi leads to
the fact that DiAM generates the same index of the next question. Otherwise, it would mean that the
answers from the NRi belong to the class of recognizable answers. Therefore, in the step function φ
for each step of the dialogue, the entire class of unrecognizable answers will be modeled with one
unrecognizable answer.
The above reasoning allows us to return to the cycle in Figure. 1, and clarify the structure of the set
of expected responses. At each step of the dialogue, the set of answers that the active agent expects
can include responses from the following three classes: (1) the class of recognizable answers; (2) the
class of unrecognizable answers (modeled by one answer); (3) the class of question detectors (to de-
termine the need for a role reversal).
Let us consider an example that will allow, firstly, to assess how useful the finite-automaton model
of the question-answer dialogue is when constructing a dialogue access method to the memory of
questions, and, secondly, will provide a transition to the subsequent model in the form of a Petri net.
The example includes several steps.
Step 1. The active agent generates a question with index Que1 and expects to receive the following
answers:
Ans1 – request for a hard copy of a question;
Ans3 – answer followed by a question with an index Que3;
Ans4 – answer followed by a question with an index Que4;
Ans5 – unrecognizable answer (any answer other than Ans1, Ans3, Ans4). Answer Ans5 means that
it is necessary to generate a question with Que2 index.
Step 2. The active agent generates a question with index Que2, which is a reformulated question
with index Que1. In this step, the active agent expects to receive the same answers as in the first step,
as well as an Ans2 answer, which is a request to return to step 1.
DiAM is described using the following formulas
ANS = {Ans1, Ans2, Ans3, Ans4, Ans5} (8)
QUE = {Que1, Que2, Que3, Que4} (9)
S = {S1, S2, S3, S4} (10)
φ : (S1, Ans1) → (S1, Que1),
(S1, Ans3) → (S3, Que3),
(S1, Ans4) → (S4, Que4),
(S1, Ans5) → (S1, Que2),
(S2, Ans1) → (S2, Que2), (11)
(S2, Ans2) → (S1, Que1),
(S2, Ans3) → (S3, Que3),
(S2, Ans4) → (S4, Que4),
(S1, Ans5) → (S2, Que2),
The step function φ, represented by mappings (11), on the one hand, describes the “logic” of ac-
cess to the memory of questions, and on the other, the “logic” of the dialogue method for solving a
certain problem. The step function can be presented in tabular form. The tabular presentation of the
step function is convenient in that it allows you to easily switch to a graphical representation of the
question-answering dialogue in the form of a state diagram. An example of a graphical representation
of a question-answering dialogue in the form of a state diagram is shown in figure 2.
Ans2, Que1 Ans1, Que1
Ans5, Que2 s1
Ans5, Que2
s2
Ans3, Que3
Ans1, Que2
Ans4, Que4
Ans4, Que4
Ans3, Que3
s3 s4
Figure 2: Question‐answering dialogue state diagram for the example described in the text
In the state diagram shown in Figure 2, the set of vertices corresponds to the set of steps of the
question-answering dialogue (or to the set of stable states), and each arc corresponds to one of the
possible options for the development of the dialogue, determined by the answer of the reactive agent.
Arcs are marked by pairs Ansi, Quei. Where Ansi – one of the expected answers; Quei – question in-
dex.
As noted earlier, the step function can be considered as a way of describing the "logic" of the dia-
logue problem solving method, and in this sense, a state diagram, an example of which is shown in
Figure 2 can be viewed as a diagram describing the behavior of an active agent in the process of solv-
ing a problem.
4. Model in the form of a Petri net
The finite-automaton model of question-answering dialogue has its own sphere of applicability
and can be used to specify a number of applied dialogue systems. However, the finite-automaton
model has disadvantages that appear at the stage of its computer implementation.
An effective approach to the computer implementation of question-answer dialog systems is the
datalogical approach, which, if applied to the design of the dialog access method DiAM, involves the
implementation of the step function not in the form of a program code, but in the form of a mapping
into a certain database. A decisive advantage of the datalogical approach is the ability to easily mod-
ify the dialogue method using full-screen editing tools. Thus, the datalogical approach excludes the
process of compiling the source code when modifying the system and allows the dialogue method to
be modified by its author.
From the standpoint of the datalogical approach, the formalism adopted to describe the dialogue
method must be identified with the conceptual model of some database. As noted in [10], the problem
of the conceptual database model is associated with such a representation of the model, which, on the
one hand, most naturally reflects the subject area (in our case, the dialogue method of accessing the
memory of questions), and, on the other hand, can be supported by computer means. In other words, a
formalism is needed that can be easily transformed into a data schema. The experience of designing
dialogue applications allows us to conclude that the noted property is inherent not in the state diagram
of the dialogue access method (an example of which is shown in Figure 2), but in the graph modeling
the dialogue access method in the form of a Petri net [11].
The Petri model of the dialogue method, like the automaton model, is based on three assumptions:
(1) the problem solved in the dialogue process can be solved in a finite number of dialogue steps; (2)
by the beginning of the solution of the problem, all questions and answers necessary for its solution
are determined; (3) modification of the current set of expected answers of the reactive agent, in any
case, generates a set of answers that is different from the current one and, therefore, has a unique in-
dex. We describe the Petri-model of the dialogue method with the following four:
DiAM = (QUE, ANS, NextQue, NextAns) (12)
QUE = {Quei}; i = 1,…,n (13)
where QUE – a collection of question indices made up of elements of the set (2), which allows the
presence of several instances of the same element [11].
ANS = {Ansi}; i = 1,…,p (14)
ANS – a collection of answers made up of elements of the set (3).
NextQue : ANS → QUE (15)
NextQue – function of subsequent question indices. Since the active agent generates only one ques-
tion at each step, NextQue determines the index of a single question for each answer.
NextAns : QUE → ANS (16)
NextAns – function of subsequent answers, which map the collection of question indices into the col-
lection of answers.
To illustrate the Petri-model, let us present the example, described earlier, by formulas (12) – (16).
ANS = {Ans1, Ans2, Ans3, Ans4, Ans5} (17)
QUE = {Que1, Que2, Que3, Que4} (18)
NextAns(Que1) = {Ans1, Ans3, Ans4, Ans5}
NextAns(Que2) = {Ans1, Ans2, Ans3, Ans4, Ans5}
(19)
NextAns(Que3) = {}
NextAns(Que4) = {}
NextQue(Ans1) = {Que1}
NextQue(Ans2) = {Que1}
NextQue(Ans3) = {Que3} (20)
NextQue(Ans4) = {Que4}
NextQue(Ans5) = {Que2}
Formulas (19) and (20) can be used to define NextAns and NextQue functions in the form of ta-
bles. The right-hand side of the i-th line of the NextAns function specifies the set of reactive agent
answers expected at the i-th step.
i i
NextAns(Quei) = R U NR (21)
The right-hand side of the i-th line of the NextQue function consists of one element of the collec-
tion Que, which is a consequence of the limitation inherent in the question-answering dialogue, which
is that for each answer from the set of expected answers, the function of indexes of subsequent ques-
tions determines the index of one single question.
In the graphical interpretation of the Petri-model of the dialogue method, the collection of indexes
of the questions Que and the collections of answers Ans are represented by sets of places (circles) and
transitions (rectangles), respectively. The set of answers Ri U NRi expected at the i-th step is repre-
sented by a set of transitions that are incident to the i-th place and are connected to it by outgoing arcs.
For the Petri-model, a step is a natural "building block" of a dialogue access method and for the i-
th step can be defined as a set
i i
Quei, (R U NR ) (22)
Figure 3 shows the graph of the Petri-model of the dialogue method, corresponding to the example
described in the text.
Ans2 Que1
Ans1
Ans5
Que2
Ans3 Ans4
Ans1
Que3 Que4
Figure 3: The Petri‐model graph for the example described in the text. The black transition simulates
all unrecognizable answers
When interpreting the Petri-model graphically, a dialogue step is a place and a set of transitions
connected to it by outgoing arcs. In Figure 3 highlights the elements included in the scope of the con-
cept of "dialogue step".
The Petri-model graph is marked with a single token marking the current active step. The initial
marking, in this case, should be understood as indicating the first step from which the implementation
of the dialogue method begins. The condition for firing a transition is the coincidence of the answer
encoded by this transition and the answer received from the reactive agent. In other words, a transition
is fired and "skips" a token if an answer is received from the reactive agent, which coincides with the
answer encoded by this transition.
The theory of Petri nets provides a convenient apparatus for tracking the dynamics of a simulated
process, consisting of marking places and conditions for firing transitions. Since, in the Petri-model of
the question-answering dialogue, there is a single token, the marking can be represented by a vector,
the number of components of which is equal to the number of elements of the collection of question
indices – the number n.
μ = (μ1, μ2, . . . μn) (23)
Each component of the vector μ takes values on the two-element set {0,1}. μi = 0 if the token is ab-
sent in the i-th place corresponding to the i-th element of the collection Que. μi = 1 if the token is in
the i-th place corresponding to the i-th element of the collection Que.
The question-answering dialogue process is accompanied by the movement of the token across the
Petri-model without destroying or multiplying it. Therefore, at any moment of the dialogue, Ʃ μi = 1
takes place. Thus, in the process of a question-answering dialogue, the dialogue method is character-
ized by a continuously changing vector μ, which indicates the current, active step of the dialogue. For
the Petri-model shown in Figure 3, the vector μ indicates step number one and has a value μ=
(1,0,0,0). To move a token to the next place, it is necessary that one of the transitions of the step fires.
Representation of the dialogue method in the form of a Petri net (formulas 12 – 16) models its spa-
tial structure and does not reflect the dynamics of the dialogue process, which is set, in the general
case, by the cognitive cycle of the question-answering dialogue process shown in Figure 1. Let us
supplement the structural description of the dialogue method with components that simulate the dy-
namics of the dialogue process. For this purpose, let us consider how, within the framework of the
proposed Petri-model, the cycle of the question-answer dialogue process is implemented, based on the
assumption that the NextAns and NextQue functions are presented in tables.
It can be assumed that a separate row in the NextAns function table corresponds to one step of the
dialogue. Each row starts with the index of the question generated at the given step, followed by a list
of answers associated with that step. In this case, the NextAns function table consists of n rows, where
n is the number of elements in the collection of question indices. The number of columns in the Nex-
tAns function table is determined by the maximum possible number of answers expected from the
reactive agent during the dialogue. Since the set of answers associated with a step is individual for
each step and is determined by the number of answers expected at a given step, some of the cells in
the NextAns table remain empty.
The NextQue function table has a simpler structure. It consists of p rows, where p is the number of
elements in the collection of answers. Each row in the NextQue function table contains two elements:
the expected answer and the associated follow-up question.
Let's add a unified DiMC process to the model, which simulates the cyclically repeating dynamics
of the dialogue
DiMC(μ, NextAns, NextQue) (24)
The unified DiMC process controls the transition from the previous step of the dialogue to the next,
which is equivalent to firing one of the transitions of the step and moving the token. The unification
of the DiMC process means that for the implementation of any step of the dialogue it is necessary to
perform the same sequence of actions, and that this sequence of actions does not depend on the sub-
ject area of the dialogue process. We describe a separate iteration of the DiMC cycle as follows.
1. The marking vector μ defines the currently active step of the dialogue process, which corre-
sponds to the row number in the NextAns function table.
2. The index of the current question is determined and transferred to the memory of questions. Us-
ing the question specifications in the memory of questions, the active agent generates and
passes the current question to the reactive agent. The active agent enters the waiting state for
the answer of the reactive agent.
3. The active agent perceives the current answer of the reactive agent.
4. The current answer of the reactive agent is processed. The perceived answer is sequentially
compared with all the answers expected at this step, stored in the cells of the selected row of the
NextAns function table. For a matched answer, a NextQue function table row is determined.
5. Using the table of the NextQue function, the component of the vector μ is searched for, which
determines the next step of the dialogue. The value of this component changes from zero to
one, and the process returns to item 1.
Among the actions iteratively performed by the unified DiMC process, there are two actions that
require more detailed consideration and clarification: (1) generating the current question; (2) process-
ing the current answer. Since DiMC is a unified process that processes any step “uniformly”, both
question generation and response processing are handled by DiMC using the same rules for any dia-
logue step in any dialogue. These rules define a certain standard model for the functioning of an ac-
tive dialogue agent. In other words, DiMC generates a question and processes the answer in a certain
standard way. It is clear that even with a fairly extensive standard, there may be cases where standard
tools are not enough. For example, when generating a question, in the case when it is presented non-
verbally, it is impossible to take into account all the diversity of non-verbal presentation of informa-
tion, and when processing the answer, specific numerical processing may be required. Therefore, in
addition to the basic DiMC process, it is rational to include in the model “external” processes in rela-
tion to DiMC. These processes must be called from DiMC and return control to DiMC when finished.
Let's call such processes process-daemons and add two classes of process-daemons to the model
QueDemon and AnsDemon
Process-daemons carry out "additional processing" of a question or answer at any step of the dialogue
process in the case when standard DiMC tools are not enough [12].
Let's consider the sphere of applicability of the Petri-model of the question-answering dialogue.
By the sphere of applicability we mean the division of problems solved in the dialogue process into
two classes: (1) easily implemented within the Petri-model and (2) difficult to implement within the
Petri-model.
Problems that are difficult to be implemented within the framework of the Petri-model include, for
example, problems that are solved when conducting psycho-diagnostic tests. As a rule, at the first
stage of psycho-diagnostic testing (in the process of dialogue interaction with the subject), a primary
data set is formed, which is then used to form a conclusion about the intellectual abilities or the struc-
ture of the subject's intelligence. An example of a psycho-diagnostic test is the Raven's progressive
matrix technique used to test intellectual abilities [13]. The dialogue process that implements the Ra-
ven's progressive matrix technique has two specific features. Firstly, at each step of the dialogue, the
reactive agent (subject of testing) is presented with stimuli-questions in a non-verbal form. Secondly,
the sequence of stimuli-questions transmitted to the reactive agent is formed by the active agent with-
out taking into account the answers of the reactive agent.
We will describe a simple psycho-diagnostic test as follows. The first step generates a Que1 ques-
tion that expects one of the answers Ans1 or Ans2. In the second step, regardless of the answer re-
ceived, a Que2 question is generated, for which one of the answers Ans3 or Ans4 is expecting. The
conclusion is determined depending on the combination of the answers received. The graph of the
Petri-model of the dialog method that implements the described test is shown in Figure 4.
μ1, Que1
●
Ans1 Ans2
μ2, Que2 μ3, Que2
Ans3 Ans4 Ans3 Ans4
μ4, μ5, μ6, μ7,
Que3 Que4 Que5 Que6
Figure 4: Petri‐model of a "difficult" dialogue method
At the bottom of Fig. 4 are target places corresponding to the end of the dialogue and the forma-
tion of a conclusion. The difficulty of implementing the Petri-model is manifested in the rapid in-
crease in the number of steps. If a answers are expected at each step, and subsequent questions do not
depend on previous answers, then the total number of steps is determined by the formula
0 1 3 b
n=a +a +a +…+a (25)
where b is the number of questions. The Petri-model for Raven's progressive matrix technique con-
sists of 261 steps. The tree-like shape of the Petri-model and a large number of steps are determined by
the fact that the model takes into account the combination of answers by forming a unique trajectory
of the token in the network. A way to combat this deficiency is to include a "history of answers"
memory into the model. The presence of such memory means taking into account the principle of the
history of answers formulated in Section 1, which means that the dialogue method, when forming the
next question, should take into account both the answer just received and the previously perceived
answers. To simplify the presentation, we will assume that the model includes the memory Mem,
which stores only one answer obtained at the previous step of the dialogue. Thus, the contents of
Mem: (1) are automatically updated when dialogue go to the next step; (2) DiMC takes into account
the contents of Mem when determining the index of the next question.
Fig. 5 shows the graph of the Petri-model with memory Mem storing the answer obtained in the
previous step. The inclusion in the model the memory of the previous answer does not require the
formation of a unique trajectory for each conclusion. The target positions remain unique, and the tra-
jectories leading to the target positions have a common part.
μ1, Que1
●
Ans1 Ans2
μ2, Que2
Ans3, Ans3, Ans4, Ans4,
(Mem = Ans1) (Mem = Ans2) (Mem = Ans1) (Mem = Ans2)
μ3, Que3 μ4, Que4 μ5, Que5 μ6, Que6
Figure 5: Petri‐model in the presence of memory of the previous answer Mem
5. Conclusion
The article describes two formal models of a question-answer dialogue: (1) a finite-automaton
model and (2) a model in the form of a Petri net. The models can be used to design a "dialogue ma-
chine" that simulates the purposeful behavior of an artificial active dialogue agent, which does not
depend on the subject area of the dialogue. The functioning of the dialogue machine is based on the
implementation of a unified cognitive cycle of dialogue. The question-answering dialogue model in
the form of a Petri net has a wider sphere of applicability than the finite-automaton model. The advan-
tage of this model is that it simulates a typical question-answering process loop using the unified
DiMC process, and also allows custom processing of questions and answers using the unique QueDe-
mon and AnsDemon processes. The model in the form of a Petri net also allows taking into account
the history of the answers of the reactive agent when forming the next question.
It is supposed to direct further research to develop the main ideas of the described models, but to
start not from mathematical structures in the form of a Mealy machine or a Petri net, but from the idea
of representing the dialogue method in the form of a network structure consisting of nodes of different
types. A priori, it is assumed that the network structure is mapped to a relational database. In such a
datalogical and network model, the following should be essential: (1) two of the three principles for
organizing a question-answering dialogue formulated in Section 1 should be taken into account: the
principle of the “depth of dialogue” and the principle of the “history of answers” of a reactive agent;
(2) a datalogical approach should be developed and, therefore, a dialogue method for solving a prob-
lem, as well as questions of an active agent, should be represented by data stored in a database.
6. References
[1] A. M. Turing, Computing machinery and intelligence, Mind, 49, (1950) 433-460.
[2] S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, 2nd ed., Prentice Hall, New
Jersey, 2003.
[3] U. Neisser, Cognition and Reality, W.H. Freeman and Company, San Francisco, 1976.
[4] N. Belnap, T. Steel, The Logic of Questions and Answers, Yale University Press, New
Haven and London, 1976.
[5] J. Hintikka, Socratic Epistemology: Explorations of Knowledge Seeking by Questions, Cam-
bridge University Press, Cambridge, 2007.
[6] A. Newell, Remarks on the relationship between artificial intelligence and cognitive psychol-
ogy, in: R. Banerji and J.D. Mesarovich (Eds.), Theoretical Approaches to Non-Numerical
Problem Solving, Springer-Verlag, New York, NY, 1970, pp. 363-399.
[7] E. Wenger, Artificial Intelligence and Tutoring Systems. Computational and Cognitive Ap-
proaches to the Communication of Knowledge, Morgan Kaufman, Los Altos, California, 1987.
[8] Zhou, L., Gao, J., Li, D., and Shum, H.-Y., The design and implementation of XiaoIce, an em-
pathetic social chatbot, Computational Linguistics 46(1) (2020), 53-93.
[9] Lawson, Mark V, Finite automata, CRC Press, Taylor & Francis Group, 2004.
[10] Graham A. A., Framework for Enterprise Data Architecture, 2nd edition, Koios Associates Ltd.,
2012.
[11] J. Peterson, Petri Net Theory and the Modeling of Systems, Prentice-Hall, Englewood Cliffs,
New Jersey, 1981.
[12] I. Chmyr, Dialogue of Partners as a Method of Non-Formal Problem Solving, in Maddy D.
Brouwer-Janse and Thomas Harrington (Eds.), Human-Machine Communication for Educa-
tional Systems Design, NATO ASI Series F129, Springer-Verlag, Berlin, 1994, pp. 222 – 228.
[13] J. Raven, Mental tests used in genetic studies: The performance of related individuals on tests
mainly educative and mainly reproductive, Master’s thesis, University of London, London,
1936.