--- title: "PAS-II: An Interactive Task-Free Version of an Automatic Protocol Analysis System" authors: - "Donald A. Waterman" - "Allen Newell" doi: "" url: "https://ijcai.org/proceedings/1973/55" pdf: "https://ijcai.org/proceedings/1973/0055.pdf" venue: "Proceedings of the Third International Joint Conference on Artificial Intelligence" year: 1973 pages: "431-444" track: "Psychology and A.I" keywords: --- # PAS-II: An Interactive Task-Free Version of an Automatic Protocol Analysis System Donald A. Waterman, Allen Newell *Proceedings of the Third International Joint Conference on Artificial Intelligence*, pages 431-444. ## Abstract PAS-II, a computer program which represents a generalized version of an automatic protocol system (PAS-I) is described. PAS-II is a task-free, interactive, modular data analysis system for inferring the information processes used by a human from his verbal behavior while solving a problem. The output of the program is a Problem Behavior Graph: a description of the subject's changing knowledge state during problem solving. As an example of system operation the PAS-II analysis of a short cryptarithmetic protocol is presented. ## Full text ## 1. Introduction Automatic protocol analysis is a joint effort by man and machine to infer from the record of the time course of a subject's behavior, the underlying information processes. As developed (5), it usually refers to the verbalizations of a subject solving some problem under instructions to think out loud. Protocol analysis designates the full range of activ­ ities engaged in by the psychologist when working with protocols: description of the subject's behavior according to an hypothesized model, induc­ tion of new rules, derivation of consequences from a model in the context of specific data, and measure­ ment of adequacy of a model. The initial focus of our work has been behavior description in terms of information processes, given an hypothesized general model (the so-called problem space in which the subject operates). The PAS-I system (14, 15) was o'ur first attempt · at automatic protocol analysis. This is a fully automatic, non-interactive, specialized system de­ signed to analyze cryptarithmetic protocols and pro­ duce as output a problem behavior graph (PBG)describ­ ing the subject's search through a posited problem space. The protocol analysis is represented as a sequence of processing stages that eventually trans­ form the raw protocol into a problem behavior graph. At each stage rules are applied which effect a trans­ formation of the data. The organization of PAS-I is shown in Figure 1. PAS-I has successfully analyzed protocols from DONALD+GERALD=ROBERT and CROSS+ROADS=DANGER crypt­ arithmetic problems. The results obtained in the DONALD+GERALD=ROBERT task for two of the subjects have been discussed in detail (15) and demonstrate that this approach to automatic protocol analysis is both feasible and rewarding. Encouraged by the success of PAS-I we have designed and built an improved version called PAS-II. PAS-II was designed with two major goals in mind: to make it interactive and task free. By interactive we mean that the user is permitted to take an active part in the ~nalysis: he can provide answers to sub­ problems the system is unable to solve, correct proc­ essing errors, and even maintain control over the processing sequence. Clearly, real-time interaction of this sort makes the system a more powerful tool ## PAS-II: AN INTERACTIVE TASK-FREE VERSION OF AN AUTOMATIC PROTOCOL ANALYSIS SYSTEM D. A. Waterman and A. Newell Departments of Psychology and Computer Science Carnegie- Mellon University Pittsburgh, Pennsylvania for protocol analysis. By task free we mean that the system is independent of any particular problem domain. To make PAS-II task free we partitioned the system into two ~arts: the problem dependent part consisting of the processing rules or heuristics used at each stage of the analysis, and the problem independent part consisting of the general control structure and command language. Thus, to apply the system to a prqtocol in a new problem area the user must first supply the system with processing rules for that domain.* The design of PAS-II also included four subgoals: to make the system transparent, modifiable, extendable, and open (see Figure 2). Two important implementation issues were not addressed in the design of PAS-II. 1). Improve system performance in cryptarithmetic. This includes expanding the deductive and inductive inference capabilities, and "fine tuning" the system by optimizing the processin& heuristics to produce the best possible analysis within the given framework. 2). Extend the scope of the analysis. For example, extend the system back to handle the speech recog­ nition and segmentation problems inherent in producing a transcription from the audio tape. Or extend the system to handle the problem of inducing the problem space from the protocol or inducing a production system model from the problem behavior graph. It was decided to make PAS-II interactive and task free, postponing the problems of increasing power in a particular task or broadening the scope of the analysis. This decision was influenced by the desire to provide a working tool for protocol analysis that could be used by participants at a workshop on New Techniques in Cognitive Research held at CMU in the summer of 1972 (7) . The PAS-II system is currently running in LISP at CMU on a PDP-10 and is available to the CMU (and the ARPA Network) community. This paper is organized as follows. The task of protocol analysis is discussed in Section 2. This is followed in Section 3 by a brief description of the structure of the program and in Section 4 by an example of its use in analyzing a cryptarithmetic protocol. Section 5 concludes with a discussion of the general executive structure of the system and its implication for AI data analysis programs. ## 2. Task of Protocol Analysis Protocol analysis is a complex data processing task requiring both deductive and inductive inference capabilities. Our current approach to protocol analy­ sis is based on a particular theory of human problem solving. For a description of this theory and an introduction to the task of protocol analysis see Newell and Simon (5). * Ultimately, a library containing processing rules for a number of different problem domains will be available to the user. Figure 1. Flow Diagram of PAS-I. ![Image](https://ijcai.org/proceedings/1973/fulltext/55/image_000000_378dffee1a477be8a4ea35240c194f25827f3dcb01139a8021ed667f08e02b0c.png) ## GOALS Interactive: Task Free ## SUBGOALS Transparent: System is easy to use and understand by virtue of a clean organization and the ability to explain itself. Modifiable : Basic changes in the data processing procedure can be made by a user with no knowledge of the language used to program the system. Extendable The programmer can easily enlarge the system to encompass a wider range of the data analysis. Open The user, rather than the program, initiates and controls the interaction and accordingly gains ultimate control of the processing sequence. User and system exchange information during processing. System is independent of any particular problem domain. Figure 2. Design Considerations for PAS-II. ## Theoretical Substructure Problem Space. We assume human problem solving takes place by search in a problem space. The ele­ ments of this space are the possible states of knowl­ edge the subject can have about the task, where a state of knowledge is simply an expression of what the subject knows at some particular point in the space. Besides knowledge states, the problem space also in­ cludes a set of operators. These define operations the subject can perform on knowledge at a particular state to yield new knowledge -- hence to move to a new knowledge state. The operators are incremental, that is, they take as input a small portion of the total knowledge state (a small set of knowledge ele­ ments) and produce as output new knowledge elements. Problem Behavior Graph. The subject's search through the problem space for a solution can be des­ cribed as a sequence of operator applications that cre­ ate a string of incrementally changing knowledge states. The plot of this search is called the problem behavior graph (PBG) · Figure 8 (also used to illustrate the output of the analysis given in Section 4) shows a problem behavior graph for cryptarithmetic. The nodes represent operator applications: the knowledge ele­ ments at the lower left of each node are the inputs, those at the lower right are the outputs. PBG branching results frqm the subject abandoning infor­ mation and returning to a prior knowledge state (usually because of a discovered contradiction). For example, in Figure 8 the outputs of nodes 4 and 6 conflict: "R is 4" conflicts with "R is odd," and leads to the abandonment of nodes 4, 5 and 6. Note that the knowledge state at any point in the graph is the conjunction of all output elements on\_ the path from the given point back to the beginning of the graph. All nodes on the path from the last node back to the beginning of the graph are called currently active nodes. Their output elements define the current knowledge state. ## Data Analysis The data being analyzed is the transcribed text of a subject's verbal protocol. As the text is trans­ formed into a PBG it is subjected to four major types of processing: linguistic, semantic, group, and PBG. Figure 1 typifies such a processing sequence. Linguistic Processing. The text is first segmented into shorter strings called topic segments, each of which is expected to ultimately yield approxi­ mately one problem space element. Each segment is then parsed using a grammar sensitive to the problem domain under consideration. The result of parsing is a set of semantic elements which represent the meaning of the segment. For example, the segment "D is not equal to 6" might yield the elements (NEG)(EQ D 6) in the cryptarithmetic task. Here (NEG) is called an indicator element, (EQ D 6) a knowledge element. Semantic Processing. The semantic elements produced through parsing are first combined in very elementary ways to produce new elements, i.e., (NEG) and (EQ D 6) become (NEQ D 6). Next, new elements reflecting relationships between elements from adjacent segments are produced. Thus, (EQ D 5) from one segment and (THEREFORE) (EQ T 0) from the next segment become (BECAUSEOF (EQ D 5)(EQ T 0)), e.g., "because D is .',i, T is 0." Finally, these elements are arranged into initial approximationsof operator groups, each containing an operator element and the surround­ ing knowledge and indicator elements. An operator group is defined to be an operator together with its iuput and output knowledge elements. Group Processing. The tentative operator groups produced during semantic processing are now analyzed to obtain a complete picture of what the subject knows at each moment and what operators he applies. First, variables in semantic elements are identified by com­ paring the elements to the current context as defined by the PBG. Thus if (EQ D 5) were in the PBG then when given the element (EQ <L> 5), where <L> stands for a class of letters, we recognize that <L> in this case is the letter D. The second part of group processing consists of finding, or hypothesizing, the origin of every knowl­ edge element in each tentative group. The origin of a knowledge element is defined to be the operator which produced it, plus the inputs to that operator, plus the operators which produced those inputs, etc. Thus the origin can be represented as a tree which defines a collection of overlapping operator groups. PBG Processing. The operator groups produced during group processing are now incorporated into the PBG. In general, each group becomes a node in the PBG. In the simplest case the new node is just attached to the last currently active node. However, when contradictions occur (the output of one node conflicts with the output of another) restructuring occurs to eliminate the conflict (see Figure 8). ## 3. Structure of the Program PAS-II takes as input a transcribed text of the verbalization of a subject solving a problem and produces as output a PBG. The processing rules for the various stages, including the rules defining the problem space, are given to the system. These rules are supplied either by the system builder via a library of rules for various problem domains or by the user himself. ## Modular Structure PAS-II is organized as a modular data analysis system. The basic unit of organization is the mode: a processing state which has associated with it a buffer capable of holding rules or data. This buffer can be modified by the editing functions available in the command language. There are three types of modes: run modes, which hold the data being analyzed, rule modes, which hold the processing rules, and auxiliary modes, which hold task-free system-oriented rules. Thus the information in the rule modes constitutes the problem dependent part of the system. The next level of organization is the stage: a unit consisting of one run mode and any number of associated rule modes. Data processing is performed in a stage by applying the rules from the rule modes associated with that stage to the data present in the run mode of the previous stage. The result of the processing is then put into the run mode of the current stage. Figure 3 illustrates the modular organization of PAS-II, with the arrows indicating data flow and the lines indicating mode associations. The highest level of organization is the processor: a unit consisting of consecutive stages in the control cycle. For example, in PAS-II two linguistic stages form the Linguistic processor and three semantic stages form the Semantic processor . Figure 3. Modular organization of PAS-II (Auxiliary modes not shown) ![Image](https://ijcai.org/proceedings/1973/fulltext/55/image_000001_e3a52982c8a3ec71b081677a7f997d1083ccaa0e53d0a0c0bc20f41804b4eaa5.png) Modes. The modes currently implemented in PAS­ II are listed in Table 1. Note that most run modes have one or two rules modes associated with them. This association is illustrated in Table 1 and also in Figure 3, * which shows the modular composition of the various processors in PAS-II. The arrows in the figure define the data links existing between modes. The mode at the tail of an arrow provides the data that the mode at the head of the arrow processes. For example, processing in the TOPIC mode involves apply­ ing the SEGMENTATION rules to the data in the TEXT mode and then placing the result in the TOPIC mode. As each line in TEXT is processed, it is deleted from the TEXT buffer. However, a copy of these deleted lines is stored elsewhere in TEXT and can be re­ trieved (see the process functions in Table 2). The arrows in Figure 3 do not necessarily define the control cycle, i.e., the order in which processing occurs. The control flow is illustrated in Figure 4 (to be discussed later). Table 1. PAS-II Modes. | MODES - RUN | MODES - RULE | MODES - AUXILIARY | |----------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------|--------------------------------------| | TEXT TOPIC LINGUISTIC 1 LINGUISTIC2 SEMANTIC! SEMANTIC2 . SEMANTIC3 GRAPHIC! GRAPHIC2 GRAPHIC3 TRACE! TRACE2 TRACE3 TRACE4 | SEGMENTATION EXTRACTION SPACE, GRAMMAR INTEGRATION NORMALIZATION GROUPING UNKNOWNS ORIGIN CONFLICT, PBG PS, MEMORY MATCH | ASSOCIATION SAVE CONTROL INFORMATION | Functions. The functions currently implemented in PAS-II are listed in Table 2. They constitute the command language available to the user, and are divided into four categories: basic, edit, flag, and process functions. Note that a mode name is a function that puts the user into that mode. A function call consists of a function name followed by its arguments. Any number of function calls may occur together. If it is not clear which names are the functions and which are the arguments, parentheses can be used for disambiguation. In ambiguous cases the system always assumes the name is a function name rather than an argument. Thus if the user types HELP TOPIC DISPLAY 3 it could mean either (HEtP TOPIC): give me information about the TOPIC mode, and (DISPLAY 3) : display line 3 of the current buffer; or (HELP): tell me how to get help, (TOPIC): put me into the TOPIC mode, and (DISPLAY 3): display line 3. The system would make the latter interpretation. * Compar1son with Figure 1 shows how PAS-II maps onto PAS-I. Note that the scope of the analysis has been extended to include a Trace processor (not discussed in detail in this paper). Auxiliary Modes. There are four auxiliary modes: save, control, association, and information. The SAVE mode contains rules which specify which mode buffers are to be saved on (or read into from) a disk file when the WRITE (or READ) command is executed. The CONTROL mode contains rules which define the control cycle for the system. Initially these rules define the control flow shown in Figures 3 and 4. The ASSOCIATION mode contains rules which define the associations between run and rule modes. The initial (or default) associations are those shown in Figure 3. The CONTROL and ASSOCIATION modes, together with the CREATE function, permit the sophis­ ticated user to create new modes, redefine mode associations, and reorganize the control flow for the entire system. One example of this is the use of a reorganized PAS-II to analyze a problem description (problem text) in natural language in order to i~fer from that text a tentative problem space, one that a subject might use in representing the problem (2). The INFORMATION mode is unique in containing no buffer and recognizing none of the functions that constitute the command language. Instead, this mode responds to key words in the users input, which may be in sentence form. The mode provides the user with general information about PAS-II: its basic organi­ zation, purpose, and techniques of operation. This is to be contrasted with the HELP function, which pro­ vides the user with specific, on-the-spot information about the mode he is in. ## Control Structure The control cycle for PAS-II is shown in the flow diagram of Figure 4. The solid arrows indicate the stage that is entered once processing in the current stage is finished. The broken arrows indicate which stage to enter before processing is started. Processing in LINGUISTIC!, SEMANTIC3, and GRAPHIC2 is incremental. In each of these modes only part of the data from the previous mode is processed at one time. This initial portion of the data is then carried through the rest of the system, leading to the growth of PBG nodes, before the rest of the data in the previous mode is processed. This is done to establish a semantic context (the PBG) as early as possible in the processing sequence so it can provide feedback * needed for linguistic, semantic, and group processing. Since the control organization of PAS-II is quite flexible, the user is under no constraints to process the data in the order shown in Figure 4. He may skip or repeat stages within the existing control framework, and may redefine the control cycle (via the CONTROL mode). He may also have the system put him into the next run mode in the control loop, or even automatically step him through the run modes, initiating the processing at each stage (see NEXT and AUTOMATIC in Table 2). ## Data Processing Figures 3 and 4 show the processors which com­ prise the control cycle of PAS-II. In the Topic processor transcribed text is segmented into phrases containing only a single task topic.** Then in the Linguistic processor an initial collection of these * At present the PBG provides feedback for group processing only. ** This is a slight extension: PAS-I requires seg­ mented text as input. | | NAME | DESCRIPTION | |----|-------------|------------------------------------------------------------------| | | (mode name) | Puts user into the mode named. | | | CREATE | Creates a new mode. | | | DISPLAY | Displays the contents of M. | | B | ERASE | Uncreates M (if it was formed using CREATE). | | A | EXIT | Takes the user out of the system (to LISP) • | | s | HELP | Provides system information pertinent to M. | | I | MODE | Tells the user what mode he is in. | | c | NEXT | Puts the user into the next appropriate run mode of C. | | | RULE | Puts the user into the rule mode associated with M. | | | RUN | Puts the user into the run mode associated with M. | | | BREAK | Breaks a line in M into two or more smaller lines. | | | CONNECT | Connects adjacent lines in M to form a single line. | | E | DEFINE | Permits the user to define the conten~s of lines in M. | | D | DELETE | Deletes lines in M. | | I | ED | Enables the user to perform intra-line editing in M. | | T | INSERT | Inserts a line after a given line in M. | | | READ | Reads data from a disk file into M. | | | RENUMBER | Renumbers the lines in M. | | | WRITE | Write the contents of M onto a disk file. | | | AUTOMATIC | Steps the user through C, executing GO in each run mode. | | | BATCH | Stops system queries during run mode processing. | | | COMMENT | Permits comments to be displayed when a line is displayed. | | F | FAST | Speeds up reading from the disk by eliminating format checking . | | L | HUSH | Abbreviates error messages. | | A | NUMBERS | Causes disk files to be written with buffer line numbers. | | G | PRINT | Puts all the I / O at the terminal onto a disk file. | | | SEARCH | Causes processing to be repeated until no rules are applicable. | | | SUPPRESS | Suppresses printing of auxiliary information during processing. | | | TIME | Causes processing time in M to be printed. | | | VERSIONl | Causes the old version of grammar / parser to be used. | | | VERSION2 | Causes the new improved version of grammar/ parser to be used. | | p | AGAIN | Puts the data in M into P and fires GO . | | R | COPY | Prints the copy of the data in M. | | 0 | GO | Processes the data located in P and puts the result into M. | | c | RECOPY | Puts the copy of the data from M back into M. | | E | RESTART | Puts the copy of the data from P back into P and fires START. | | s | START | Deletes the data in M and fires GO. | | s | | | KEY M: mode buffer of the mode the user is in P: mode buffer prior to M in C C: control cycle Figure 4. Flow diagram of PAS-II ![Image](https://ijcai.org/proceedings/1973/fulltext/55/image_000002_a3dcc01576d6068dff27c0e20226de31d2b7f0b833a3f7266979ad2e1f4d8f96.png) Key : -stage to enter after processing ----· stage to enter before processing segments is parsed yielding sets of semantic elements. These elements are processed and refined in the Semantic processor to produce groups composed of one operator element and its associated input and output knowledge elements. In the PBG processor these groups are incorporated into the PBG. The Trace processor is then used to compare this PBG with the trace produced by a given production system model of the subject. Topic Processor. The Topic processor contains two run modes: TEXT and TOPIC. TEXT is an initiali­ zation mode; it holds the data for TOPIC to process. Thus no real processing takes place in it. The TOPIC mode uses the SEGMENTATION rules to segment all the text in the TEXT mode. These rules have the general form: string 1 / string 2 , where a string is any sequence of words, punctuat~on marks, or word classes (as defined in the GRAMMAR mode), including the null sequence. The slash (/) indicates where the text is to be broken, i.e., after every occurrence of string 1 that is immediately followed by an occur­ rence of string 2 . Figure 6 show SEGMENTATION rules for cryptarithmetic (to be used in the example in Section 4) . Linguistic Processor. The Linguistic processor­ cont3ins two run modes: LINGUISTIC! and LINGUISTIC2. In LINGUISTIC! the EXTRACTION rules are used to select a consecutive set of segments from TOPIC, representing an initial guess as to the minimum number of segments from which a group can be inferred. Processing con­ sists only of transferring these segments from the TOPIC mode to the LINGUISTIC! mode. At present, the EXTRACTION rules are simply a single integer speci­ fying how many segments to transfer. Processing in the LINGUISTIC2 mode consists of applying the SPACE and GRAMMAR rules to all the topic segments in LINGU.ISTICl. The parsing operation pro­ duces, for each segment, a set of semantic elements representing the meaning of the segment. The rules in tbe SPACE mode define the problem space and have · thE form:* (semantic-element) type, where a semantic element is either an operator, knowledge, or indicatcr element* and the type is either OP, KN, or IND. The �~~ * rules define a key-word grammar and have the form: <class>= (item 11 item 12 ..· ) (item 21 item 22 ... ) ... , where an item is either a class (denoted by angle brackets) or a literal (such as a word, letter, or character). An asterisk(*) can be used between any two items to indicate a match with any string of text, and any GRAMMAR rule which is a disjunction of single literals can be written without parentheses. Figure 6 shows SPACE and GRAMMAR rules for cryptarithmetic. * SPACE rule 8 in Figure 6 is an exception. It defines a set named <V> containing two members, the class <LETTER> and the class <CARRY>. ** Two parsers are available, a simple top down parser and a more sophisticated parser written by M. Rychener. Semantic Processor. The Semantic processor contains three run modes: SEMANTIC!, SEMANTIC2, and SEMANTIC3. In SEMANTIC! the INTEGRATION rules produce new elements by combining semantic elements generated from the same or adjacent segments. In SEMANTIC2 the NORMALIZATION rules map knowledge and indicator ele­ ments into single elements reflecting the relationships existing between two or more knowledge elements. In SEMANTIC3 a tentative operator group (protogroup) is formed. The INTEGRATION AND NORMALIZATION rules are' replacement rules of the type A=> B, i.e., replace A with B. Both A and B can be lists of semantic elements. A slash (/) indicates that the next elements of the list occur on the next line of the mode buffer. Class names and X's are used as vari­ ables, and in the NORMALIZATION rules A'~ are vari­ ables which stand for knowledge elements on adjacent lines connected by the AND indicator. Typical INTEGRATION and NORMALIZATION rules for crypt­ arithmetic are shown in Figure 6. GROUPING rules are not shown.* They define a protogroup to be the largest consecutive sequence of elements containing no more than one operator element. Group Processor. There are two run modes in the Group processor: GRAPHIC!, and GRAPHIC2. GRAPHIC! processing fills in the values of variables in the semantic elements by comparing the element containing variables with all the elements currently active in the PBG, i.e., the current context. When a-match is found the appropriate values are filled in. Currently the UNKNOWNS rules are not accessible to the user. Processing in GRAPHIC2 is a joint man-machine effort.** The goal is to hypothesize for each knowl­ edge element its origin, i.e., the operator and its inputs (and the operators that produced those inputs, etc.) that produced that knowledge element as output .. The system queries the user asking for possible operators and inputs that could have produced the element whose origin is being sought. From this information the system constructs an origin tree, and hypothesizes which path through the tree repre­ sents the actual origin of the element. The path is picked on the basis of the agreement between the hypothesized inputs and the actual context defined by the current PBG. The ORIGIN rules, like the GROUPING and UNKNOWNS rules, are currently not accessible · PBG Processor. The PBG processor contains one run mode: 'GRAPHIC3. In the GRAPHIC3 mode, processing consists of taking the operator groups produced in GRAPHIC2 and :tncorporating them into the problem behavior graph. The CONFLICT rules are used to deter­ mine whether or not any knowledge elements in the operator groups conflict with knowledge already in the PBG. If such a conflict occurs, the PBG rules are used to restructure the PBG so the conflict is eliminated. At the current stage of development the Grouping rules have not been made accessible to the user. ** This is the major place where we have not regained in PAS-II the power for automatic processing available in PAS-I. Both the CONFLICT and PBG rules are ordered production rules of the formS ~ A, i.e., in situation S take action A (12, 13). A situation is defined by a list of values of certain variables, called the state vector, SV. The left side of each production rule has the form (v 1 v 2 v 1 ··· ), where V repre­ sents a permissible value lor the nth stat~ vector variable. The right side has the form (A 1 A 2 A 3 ..· ), where the A's represent actions to be taken. The cur­ rent values of the state vector variables are compared with the left side of each production rule. The first match, from top to bottom, determines the actions to be taken (an asterisk is considered to match any value). Figure 6 shows CONFLICT and PBG rules for cryptarithmetic. The CONFLICT rules determine whether or not two given knowledge elements conflict. The example CONFLICT state vector contains: (SAME 2), which is true (T) if the second items of both the elements are identical and false (F) otherwise; (ITEM 1 1 ), which returns as a value the first item of the first 'element (the element in the PBG); and (ITEM 1 2 ) , which returns as a value the first item of the second element (the element in the group) · Thus if the two elements being compared were (ODD R) and (NEQ R 5) CONFLICT rule 3 would match the state vector and the decision would be that no conflict exists. The PBG rules determine the type of restruc­ turing that occurs once a conflict is detected. The PBG state vector in Figure 6 has 2 variables: TYPE, which has the value CON if restructuring is ba~ed on conflict and SIM if it is based on similarity; and (ITEM 1 2), which is defined above. The actions shown in Figure 6 are BLOCKREJ, a type of restructuring where blocks of adja.cent nodes are abandoned, and COPY; a specification that the group causing the restructuring should remain in the active portion of the PBG after restructuring. The state vectors for CONFLICT and PBG may contain variables and actions other than the ones shown in Figure 6. For a complete description of these rules see the PAS-II reference manual (16). Trace Processor. The Topic, Linguistic, Semantic, Group and PBG process~s comprise the major portion of PAS-II. It is this portion which repre­ sents a generalized version of PAS-I. The Trace processor is a new extension to the system and has no analogue in PAS-I. Some parts of it, like the MATCH mode, are still under development. The Trace proc­ essor enables the user to write a production system model of the subject (6) , and then compare the trace obtained by running the production system model with the PBG obtained by analyzing the protocol. The details are described elsewhere (16) . ## 4. Example of Program Operation To illustrate the use of PAS-II, we present a listing of the actual user-machine interaction in­ volved in the on-line analysis of a short crypt­ arithmetic protocol. The cryptarithmetic task is given in Figure 5. Boththe protocol and the crypt­ arithmetic rules used for this example are shown in Figure 6. The protocol is stored in the TEXT mode and the cryptarithmetic rules in the eight rules modes shown. These rules approximate the minimal set needed to analyze the given protocol, and are for expository purposes only.* * The PBG rules are also used for restructuring when similarities (identical nodes) are detected, as discussed in an earlier paper on PAS-I (15). The annotated listing is shown below. The user input is in lower case and the system output in upper case. The system prompts the user by typing either an asterisk (*) or a question followed by a question mark (?). ![Image](https://ijcai.org/proceedings/1973/fulltext/55/image_000003_067d92e8b5a5a38f68491d2d7cf781b41500d09f5d901e2d5ccd5e930aa20e08.png) The above expression is a simple arithmetic sum in disguise. Each letter represents a digit, that is, 0, 1, 2, ·.· , 9. Each letter is a distinct digit. You are given that D represents the digit 5; thus, no other letter may be 5. What digits should be assigned to the letters such that when the letters are replaced by their corres­ ponding digits the above expression is a true arithmetic sum? Figure 5. Cryptarithmetic Task The user first entered the TEXT mode and dis­ played its contents. He then entered the next mode in the control cycle, TOPIC, and started processing by typing GO. This caused the SEGMENTATION rules to be applied to the data in TEXT. The system indicated that the data in line 1 of the previous mode had been transformed into the seven lines shown above, and asked if this transformation was satisfactory (OK?). At this point the user typed yes, telling the system to actually put those seven lines into the next seven * At least four times as many rules would be needed for a complete set (15) · ## TEXT MODE 1. D IS 5 ; THEREFORE T IS 0 · ASSUME R EQUALS 4 · SINCE YOU CARRY 1 , R IS ODD · ASSUME R IS 7 , NOT 5 · ## SPACE RULES - l. (NEG) IND 2. 2 . (ODD <V>) KN 3. 3 . (EQ <V> <DIGIT>) KN 4. 4 . (THEREFORE) IND 5. (BECAUSE) IND 6. (ASSUME) IND 7. (DIGIT <DIGIT>) KN 8. 8 . (<V> <LETTER> <CARRY>) SPASET ## GRAMMAR RULES 1. <EQ> = (<CARRYEQ>) (<LETTER> *<EQUAL> *<DIGIT>) 2. <CARRYEQ> " (<CARRY> * <DIGIT>) (<CARRY>) 3. <ODD> = (<LETTER> * <EQUAL> * ODD) 4. <EQUAL> " IS EQUAL EQUALS BE WAS ARE 5. <NEG> = CANNOT NOT NO N'T 6. <THEREFORE> " THEREFORE IMPLIES 7. 7 . <ASSUME> · ASSUME ASSUMING 8. 8 . <BECAUSE> = BECAUSE SINCE 9. <CARRY> " CARRY CARRYING CARRIED 10. <LETTER> " A B D E G L N 0 R T 11. 11 . <DIGIT> " 0 1 2 3 4 5 6 7 8 9 ## SEGMENTATION RULES 1. ·I 2. ; I 3. <DIGIT> ' I 4. 4 . <LETTER> ' I ## EXTRACTION RULES ## 1. 12 ## INTEGRATION RULES 1. (X 1 CARRY X2) "> (X 1 <C> X2) 2. (EQ X1 X2) I (DIGIT X3) => (EQ X1 X2) I (EQ X1 X3) 3. (NEG) (EQ <LETTER> <DIGIT>) => (NEQ <LETTER> <DIGIT>) 4. (ASSUME) (EQ <LETTER> <DIGIT>) => (AEQ <LETTER> <DIGIT>) ## NORMALIZATION RULES - l. A 1 I (THEREFORE) A2 => (BECAUSEOF A1 A2) 2. (BECAUSE) A1 I A2 "> (BECAUSEOF A1 A2) ## CONFLICT RULES 1. SV = ((SAME 2) (ITEM 1 1) (ITEM 1 2)) 2. (F * *) => NO-CON 3. (* ODD NEQ) => NO-CON 4. (* * *l => ASK-IF-CON ## PBG RULES 1. SV = (TYPE (ITEM 1 2)) 2. (CON NEQ) => BLOCkREJ 3. (CON *l => (BLOCKREJ COPY) 4. (* *l => BI-OCKREJ Figure 6 . Cr yptari t hme t ic Rules. lines of the TOPIC buffer. If the processing had been unsatisfactory, the user could have jumped to the SEGMENTATION mode, changed the rules, jumped back to TOPIC, and reprocessed the data using the new rules before proceeding with the next processing step. The user then entered the next mode, LINGUISTIC!, and started processing. The EXTRACTION rules were applied to the seven lines of data in TOPIC and the system indicated that the processing should consist of placing these lines in LINGUISTIC! unchanged. Note that the system indicated that line 1 from TOPIC was transformed into a single line in LINGUISTIC!, etc., as opposed to the previous step where one line in TEXT was transformed into seven lines in TOPIC. ``` LINGUISTIC2 MODE D IS 5 1. CEQ D 51 FROM : D IS 5 ; .IK? yes batch suppress BATCH=T SUPPRESS=T 2 . CEQ T 91 FROM : R IS ODD 6. CEQ R 71 CRSSUME I FROM : ASSUME R IS 7 7. (NEG> 3. 1 I 5. COOO Rl 6. CREQ R 71 7 . CNEQ R 51 ·OK? yes SEMANTIC! MODE FINISHED ``` ``` SEMRNTIC2 MODE RULES APPLIED 1 1-7. 111 ·ccODD Rill SEMANTIC2 MODE FINISHED SEMANTIC3 MOOE 1. CBECAUSEOF ((EQ 0 5)) «EQ T 81 l I 2. CREQ R 41 3. 1)) ( CODD Rll I 4. (AEQ R 71 5. lll «ODD Rll l FROM 1 ll l C ) KN 3 . (EQ ) KN 4 . (THEREFORE) IND 5 . (BECAUSE) IND 6. (ASSUME) IND 4. DIGIT ) KN 8 . ( ) SPASET GRAMMAR RULES 1. = () ( * *) 5. " ( * ) () 6. = ( * * ODD) 7. " IS EQUAL EQUALS BE WAS ARE 5 . = CANNOT NOT NO N'T 6. " THEREFORE IMPLIES 7 . • ASSUME ASSUMING 8 . = BECAUSE SINCE 8. " CARRY CARRYING CARRIED 9. " A B D E G L N 0 R T 11 . " 0 1 2 3 4 5 6 7 8 9 SEGMENTATION RULES 1. •I 2. ; I 3. ' I 4 . ' I EXTRACTION RULES 1. 12 INTEGRATION RULES 1. (X 1 CARRY X2) "> (X 1 X2) 10. EQ X1 X2) I (DIGIT X3) => (EQ X1 X2) I (EQ X1 X3) 3. (NEG) (EQ ) => (NEQ ) 11. ASSUME) (EQ ) => (AEQ ) NORMALIZATION RULES l. A 1 I (THEREFORE) A2 => (BECAUSEOF A1 A2) 12. BECAUSE) A1 I A2 "> (BECAUSEOF A1 A2) CONFLICT RULES 1. SV = ((SAME 2) (ITEM 1 1) (ITEM 1 2)) 13. F * *) => NO-CON 3. (* ODD NEQ) => NO-CON 4. (* * * 14. ASK-IF-CON PBG RULES 15. SV = (TYPE (ITEM 1 2)) 16. CON NEQ) => BLOCkREJ 17. CON *l => (BLOCKREJ COPY) 18. * *-OCKREJ . Cr yptari t hme . 19. Davies, D. J. M., POPLER: a POP-2 planner. MIP. School of University of Edinburgh. 20. Hayes, J. R., and Waterman, D. A., Automatic Problem Space Construction, Psychology .Department, Carnegie-Mellon University, 1973. 21. Hewitt, Carl, Description and theoretical analysis of planner: A language for proving theorems and manipulating models in a robot. AI report TR-258 (Ph .D. thesis), MIT AI Laboratory, Cambridge, Massachusetts, 1972. 22. Newell, A., Heuristic programm~ng: Ill-structured problems, in Aronofsky, J. S. (ed.) Progress in Operations Research, vol . 3, Wiley, 1969, pp. 362 -414. 23. Newell, A., and Simon, H. A., Human Problem Solving, Prentice-Hall, Englewood Cliffs, N.J. 1972. 24. Newell, A., A theoretical exploration of mechanisms for coding the stimulus, in Melton, A. W., and Martin, E. (eds.) Coding Processes in Human Memory, Winston and Sons, Washington, D.C., 1972, pp. 373-434. 25. Newell, A., Simon, H. A., Hayes, R., and Gregg, L., Report on a workshop in new techniques in cognitive research. Computer Science Department, Carnegie- Mellon University, 1972. 26. Rulifson, J. F., Derksen, J. A., and Waldinger, R. J., QA4 : A procedural calculus for intuitive reasoning, Stanford Research Institute, November 1972. 27. Stone, P. J., Dunphy, D. C., Smith, M. S., Ogilvie, D. M., The General Inquirer, MIT, Cambridge, Massachusetts, 1966. 28. Sussman, Gerald, and McDermott, Drew, Why conniving is better than planning, MIT, Cambridge, Massachusetts, April 1972. 29. Sussman, Gerald, and McDermott, Drew, Conniver Reference Manual, MIT, Cambridge, Massachusetts, May, 1972. 30. Waterman, D. A., Machine learning of heuristics. Ph.D. Thesis, Computer Science Department, Stanford University, 1968. 31. Waterman, D. A., Generalization learning tech- niques for automating the learning of heuristic~ Artificial Intelligence, vol. 1, nos. 1 and 2, 1970, pp. 121-170. 32. Waterman, D. A., and Newell, A., Protocol analy- sis as a task for artificial intelligence. Artificial Intelligence, vol. 2, nos. 2 and 3, 1971, pp. 285-318. 33. Waterman, D. A., and Newell, A., Preliminary results with a system for automatic protocol analysis. Carnegie-Mellon University, Computer Science Department, 1973. 34. Waterman, D. A., PAS-II Reference Manual, Psychology Department, Carnegie-Mellon University, 1973.