[Next] [Up]
Next: About this document Up: Content



A form of reasoning by which, given a fact or state, we can hypothesize some prior fact or state which might have given rise to it. For example, if we know that the streets are always wet after it has been raining, and that the streets are wet now, we can guess that it has recently been raining. The streets could be wet, of course, for some other reason entirely, so abduction is not always a reliable form of reasoning. See also Logic, Rules of Inference.

A list of possible tasks for a system to perform, ordered according to usefulness. An agenda may be used, for example, in a search program to determine the next path to investigate.

A fixed set of operations on numbers or symbols - of a sort that can be automated on a digital computer. See also Heuristic.

Analogue computer
See Digital/Analogue Computer.

In an analogical representation there is a direct correspondence between the important properties of the representation and the properties of the domain -- for example, by using a 2-dimensional array to represent a 2-dimensional picture.

Nodes in a semantic network are connected by labelled directed arcs (also sometimes called links or pointers), which indicate the nature of the connection between adjacent nodes. In isa-hierarchies, the most basic links are taxonomic (isa) and partonomic (ispart) relations; others name features or attributes; their values are given by the node pointed to by the link.

(As applied to computers), the structured organization of elements in a computational mechanism -- for example, the difference between sequential processing and parallel distributed processing machines is said to be a difference in architecture. See also Computation, (non-) von Neumann Architecture.

A procedure may take input values and produce output values. The former are called the procedure's arguments; the latter its results. Thus the POP-11 procedure call length([1 2 3]) has one argument (the list [1 2 3]) and produces one result (the number 3). In logic, an argument represents individual entities, such as `John', or `apple'. A predicate is applied to one or more arguments to produce a formula. See also Axiom/Theorem.

A data object consisting of an ordered series of elements that can be accessed by number index.

The widely used American Standard Code for Information Interchange (ASCII Code) assigns a number to each character that can be typed on a computer keyboard. The code aids programming and communication between computers.

The operation in computer programming of giving a value to a variable.

An attribute (or feature, or property) is a distinguishing aspect, quality, or characteristic of an object. An attribute of a canary, for example, is yellowness.

Most logical systems contain fundamental propositions or axioms, which cannot themselves be justified from within the system itself. Any conclusions derived from these axioms by the system's rules of inference are called theorems. See also Logic, Predicate Calculus/Predicate Logic, Propositional Calculus.

Returning to a previous state in a computation in order to try an alternative strategy. In terms of a search tree, backtracking occurs when the end of a branch is reached without a solution being found, and a different branch is chosen.

Backup Memory
See Main Memory/Backup Memory.

Behaviourism/Behavioural Psychology
An influential twentieth-century school of thought in psychology and in the philosophy of mind that claimed that only the outwardly observable aspects of human behaviour produced scientific data for the study of the mind. Behaviourists thus rejected introspectionism.

Binary Digit (Bit)
Most modern computers use the binary counting system -- employing only 1's and 0's -- to represent any number or other character. Binary numbers can be easily stored in electronic form. See also Central Processor.

A data object which represents whether some condition is true or not. There are only two such objects: <true> and <false>.

Branch and Bound
A search strategy in which the `lowest cost' node in the agenda is always considered first. This strategy is guaranteed to find the lowest cost solution if more than one solution to a problem exists.

See Conditional.

A search strategy in which each level of the search tree is considered in turn. All the nodes at any given level of the search tree are considered before any nodes at a deeper level.

Most programming languages have a variety of terms which are primitive to the language; these are the built-in terms. Many languages, such as POP-11, allow you to define your own terms or procedures. These are known as user-defined terms.

Calling a Procedure
Instructing a computer to interpret the series of instruction defined in a procedure. See also Argument/Result.

Case/Case Relationship/Case Slot
The case is the functional relationship of noun-phrases to the main action of sentences as expressed in the verb. Every verb has a certain number of case slots. For example, the verb `cut' presupposes someone cutting (the `agent' case slot), something cut (the `object'), and something with which the act of cutting is performed (the `instrument').

Central Processor
That part of a conventional digital computer which performs the direct operations upon sequences of sysmbols stored as sets of binary digits (bits). See also Architecture, Compilation/Interpretation, Computation, Hardware, Main Memory/Backup Memory, Parallel Distributed Processing, Sequential Processing, Software.

The relation of nodes to the node that immediately dominates them in an isa hierarchy is that of children to a parent node. See also Taxonomic Tree.

In contrast to behaviourism this school of thought claims that psychology should be concerned with a person's internal representations of the world and with the internal or functional organization of the mind. See also computationalism, functionalism.

Procedural programming languages such as POP-11 are composed of statements that can be interpreted as commands to the computer to perform various operations -- for instance. adding two numbers and assigning the result to a variable.

A commutative relation in a semantic network is one which is symmetric. That is, for any relation R, if xRy is true, then yRx is also true. For example, if Frank is married to Hilda, then Hilda is also married to Frank.

Competence Knowledge
An abstract description of the knowledge characterizing a particular domain. See also Performance Knowledge.

A person's linguistic competence is the ability to produce and understand an indefinite number of novel sentences, to detect ambiguities, and to recognize grammatical errors. Performance refers to a person's use of language in particular situations. The distinction is mirrored in natural language processing by grammars, which are usually stored declarative representations of the rules governing the well-formedness of sentences, and parsers, which are programs that process utterances by reference to such rules.

Two widely adopted methods for converting the instructions of a program into binary machine code instructions specifying basic operations on the machine's central processor. Compilation involves converting a program as a whole, whereas interpretation involves translating each instruction singly.

Compiled Representation
A representation of human knowledge in the form of an automatic process that runs without calling on declarative knowledge nor making demands on working memory.

The principle that the meaning (or semantic value) of a sentence is a function of the meanings of its constituents together with their mode of combination (just as the meaning of a complex expression in propositional calculus is a function of the truth-value of the atomic propositions together with the truth-functional connectives by which they are combined together).

The manipulation of numbers or symbols according to fixed rules. Usually applied to the operations of an automatic electronic computer, but by extension to some processes performed by minds or brains. See also Cognitivism.

The notion that the operation of the mind can be explained entirely in terms of the formal, or functional, properties of a computational system. See also Cognitivism, Eliminativism, Functionalism, Materialism, Turing Test.

A machine for performing operations on numeric or symbolic data. Nowdays the term usually refers to digital computers capable of being instructed by stored programs. See also Algorithm, Hardware, Software.

A concept is a stable mental representation of objects, classes, properties, and relations. When we encounter a new object or event for the first time, we draw upon our mental store of concepts in order to identify it. One of the most important parts of the human learning process is concept-formation, where, after a number of distinct experiences of the `same' object or event, we acquire, by a process of induction, a concept for it.

Conceptual Dependency Representation
A formalism for representing the meanings of sentences, in a manner similar to that of a semantic network, as structured configurations of basic language-independent conceptual elements, or conceptual primitives. See also Knowledge Representation, Semantics.

Conceptual Primitive
One of a small number of fundamental sorts of action or event, such as the physical movement of an object (ptrans) or the transfer of some mental content (mtrans). Used in conjunction with scripts as a method of knowledge representation.

Used to describe an instruction, or a sequence of instructions, that is only to be executed when certain specified conditions are met. For instance, the Automated Tourist Guide should only print information about the river when the user has asked a question about the river. Programming languages often introduce a conditional instruction by means of the word if. The possibility that a program can carry out different actions under different circumstances is called branching.

Conflict Resolution Strategy
A strategy used by a production system interpreter for deciding which production rule is to be fired if the heads of more than one rule match the contents of working memory.

Connectionist Model/Neural Network
A system consisting of a network of processing units each of which carries out a simple computation. The units are all interconnected and knowledge is represented as patterns of connection. See also Parallel Distributed Processing.

See Variable/Constant.

Data Object
Computer programs involve operations on different kinds of symbolic entities, known as data objects or types. In POP-11 the data objects include numbers, words, booleans, and lists.

Data Structure
A specific data object used as an object of computation.

A means of recording and accessing large amounts of relatively simple items of data, such as bibliographical information. In POP-11 the database package contains a set of built-in procedures for accessing list-structured items.

A declarative representation contains knowledge in the form of facts or images. In a procedural representation, knowledge is stored as processes or procedures. Different programming languages can be characterized as having a declarative or procedural style. See also Procedural, Prolog, POP-11.

When a variable name is declared by means of the vars instruction, POP-11 enters the word in its list of variable names and allocates memory for the variable.

A form of logical reasoning by which, from a given set of facts (premises), certain consequences (conclusions) can be inferred. For example, if I know that on every occasion on which it rains the streets get wet, and that it is raining now, then I can deduce that the streets are now wet.

To specify the set of instructions associated with a procedure, as used in computer programming.

Deictic Expression
An expression which picks out some individual, time, or place relative to the context of utterance. For example, `I', `you', `here', `these', `yesterday' have no intrinsic semantic value; the reference of each on an occasion of speech is determined by the appropriate component of the speech situation.

A type of procedure associated with a frame. The two main types are if-needed and if-added demons.

A search strategy in which all the nodes on one branch of the search tree are considered before backtracking to try nodes on other branches. All the successors of a given node are considered before any other nodes at the same level as the given node.

Digital/Analogue Computer
An analogue computer uses continuously variable quantities, such as voltages, to represent similarly varying enities in the domain. Digital computers operate upon discrete, coded symbols.

Distinguished Symbol
In a generative grammar, the distinguished symbol is the only non-terminal symbol which can appear at the root of a parse-tree. It is conventionally `S' for `sentence'.

Distributed Processors
See Parallel Distributed Processing.

Two syntactic items have the same distribution if they can be substituted for each other in the same context within a sentence.

The area of enquiry and associated tasks to which an artificial intelligence system is applied. (For instance, MYCIN has as its problem domain the diagnosis of blood disorders.) See also Domain-Independent/Domain-Specific Knowledge, Heuristic, Knowledge-Based System.

Domain-Independent/Domain-Specific Knowledge
Many artificial intelligence systems operate within a specific domain -- i.e., their knowledge is mainly domain-specific. However, they may also contain domain-independent knowledge, in the form of principles of common sense, or general scientific laws common to many areas of expertise.

A philosophical theory of mind associated with the philosopher Descartes according to which human beings are constituted by two distinct metaphysical substances or realms: Thought and Extension. See also Functionalism, Materialism.

Dynamic Value
In game playing, the estimated value of a state, arrived at by considering the results of a static evaluation function applied to possible future states. These static values are propagated back in time using, for instance, a minimax strategy.

An image contour along which intensity changes abruptly.

Edge Element
The smallest piece of edge detectable by examining neighbouring pixels in an image.

Edge Map
A 2-D array recording the position of edge elements derived from an image. Typically there is a one-to-one correspondence between array cells and image pixels at the centre of edge elements.

An approach to understanding the mind in which it is claimed that terms like `beliefs' and `intentions' belong to an outmoded `folk-psychology' and are not capable of scientific justification. See also Functionalism, Intentional System/Intentional Stance, Materialism.

A program which can be taught to respond to sentences typed by a user in a way that can give the illusion of understanding them, but which in fact relies on pattern matching and substitution to produce answers based on a pre determined set of stock phrases. ELIZA was originally developed by Joseph Weizenbaum in the mid-1960s, and now serves as a demonstration of the technique and as a warning against taking the responses of a computer at face value.

When a syntactic constituent has another of the same category nested within it as one of its constituents, the nested constituent is said to be embedded within the larger one.

To perform an operation on given arguments producing a canonical (or simplified) result. For example, given an appropriate definition for the procedure maximum, the expression maximum(5,7) will evaluate to 7.

Expert System
A computer program that incorporates the rule-governed expertise of human experts such as doctors, engineers, or economists within a restricted problem domain. See also Heuristic, Knowledge-Based System.

In a computer program, a combination of data objects linked by operators.

See Attribute/Feature/Property.

(Pertaining to production rules.) See Trigger.

Flow of Control
The sequential behaviour of a program, as it carries out the processing of input.

Formal semantics
A theory of meaning based on the analysis of a natural language as though it were a formal language, such as the propositional and predicate calculi. Typically, it is truth-conditional and compositional.

A set of symbols and a collection of systematic rules governing their uses and interrelations. See also Knowledge Representation, Logic.

In predicate logic a formula consists either of a predicate applied to one or more aguments, or a combination of such `atomic' formulae linked by the connectives `not', `or', and `and'. See also Axiom/Theorem.

Frame systems are a particular kind of knowledge representation formalism, consisting of structured descriptions of stereotyped objects or situations, with slots filled in with particular values. See also Demon, Script.

A philosphical view of mind according to which mental processes are characterized in terms of their abstract functional (opr computational) relationships to one another, and to sensory inputs and motor outputs. See also Cognitivsm, Computationalism, Eliminativism, Turing Test.

A formal set of rules which explicitly defines the grammatical sentences of a language is said to generate that language. Such a set of rules constitutes a generative grammar.

A generic term is one which picks out a class of individuals, or the prototype of the individual, rather than the individual itself. For example, in the sentence ``The wolf has disappeared from northern Europe,'' we are referring to the genus rather than to a particular wolf.

A grammar may be informally thought of the set of words and category symbols in a language, together with the rules governing their combination into sentences. It is, in human terms, what speakers know of their language independent of their ability to use that knowledge. See also Competence Knowledge, Competence/Performance, Syntax.

A grammatical sentence is one which is well-formed with respect to the rules (`grammar') for generating the sentences of the language. See also Syntax.

A numerical measure of the intensity of a single pixel. The number is typically an integer between 0 and 63 or 0 and 255, where 0 signifies minimum intensity and 63 or 255 signifies maximum intensity.

The physical machinery of a computer and its associated devices. See also Algorithm, Central Processor, Computer, Program, Software, Visual Display Unit (VDU).

A rule of thumb which may help in solving a problem, but is not guaranteed to find a solution. A method for cutting down useless searching amongst possibilities. Heuristics provide much of the knowledge contained in expert systems. Constrasts with algorithmic procedures. See also Knowledge-Based Systems.

Heuristic Search
Any search strategy which makes use of heuristics to suggest the best nodes to consider at each stage of the search.

A form of reasoning by which we derive general principles from particular facts or instances sharing common properties. For example, if all ravens of which we have had experience are black, then we might inductively reason that all ravens are black.

Information Processing System
Generally speaking, any system which operates on symbolic data given as its input so as to generate an appropriate output. See also Computer, Program.

See Property Inheritance.

(a) The values that are passed into a procedure, and which are returned as the results of the operation of a procedure.
(b) In general, those aspects of a computer system which involve the transmission of data into the system, and the communication of results back to the outside world. See also Argument/Result, Calling a Procedure.

Intentional System/Intentional Stance
Some philosophers claim that intentionality should be understood instrumentally as a feature of certain kinds of systems; these would include intelligent computers as well as people. It is necessary use terms such as `intending', `believing', `wanting' in order to explain the behaviour of such systems. Adopting this `intentional stance' does not commit one to believing that there really are intentional states as such. See also Cognitivsm, Computationalism, Eliminativism, Functionalism, Turing Test.

The quality of `aboutness', or `world-directedness', that has been claimed to be a distinguishing feature of mental processes as opposed to physical ones. It has been proposed that `intelligent' computer performances possess only a secondary, or derivative, intentionality: this has been used as an attack on the pretensions of artificial intelligence to explain the human mind. See also Computationalism, Functionalism, Intentional System/Intentional Stance, Turing test.

Internal Representation
A symbolic representation in a computer of the states and processes of problem solving, search, etc. See also Cognitivsm, Knowledge Representation.

See Compilation/Interpretation.

A process of inward attention or reflection, so as to examine the contents of the mind. Introspectionism, as a method in psychology, is contrasted with, and was supplanted by, behaviourism.

isa Hierarchy
A series of nodes joined by links of the form `X isa Y' in semantic networks, which allow efficient forms of inference. See also Knowledge Representation, Property Inheritance, Structural Description.

In a program based on pattern matching, a keyword is a word in the input sentence which determines the actions to be taken. In a simple program such as ELIZA, recognition of a keyword may completely determine the response of the program; in more sophisticated programs the keyword may determine the context in which further analysis is undertaken.

Knowledge Representation
The term used in artificial intelligence to cover the study of formalisms which model human forms of knowledge. See also Frames, Predicate Calculus/Predicate Logic, Production Systems, Scripts, Semantic Networks.

Knowledge-Based System
A computer program which represents relatively complex kninds of information, often as rules governing judgements in particular problem domains. See also Database, Expert System, Knowledge Representation.

Lexical Category
Every word in the language belongs to some lexical category, that is, instances some part of speech. Thus, `dog', `brain', and `syllogism', for example, all belong to the lexical category `noun'.

The lexicon of a language is dictionary of all the words in the language, and may contain many types of information about each word, for example, what part of speech it is (its lexical category), and what its distributional properties are.

See Arc/Link/Pointer.

A programming language that uses the list as its primary data object. The most widely used language for artificial intelligence.

A special kind of data object, found in POP-11 and other artificial intelligence languages. A list consists of a sequence of zero or more elements, each of which may be any kind of data object (including another list).

In POP-11 procedures, variables can be defined as local to a given procedure. These variables lose their values outside the context of the procedure itself. Global variables, however, retain their assigned values after the procedure terminates.

The study of formal principles of rasoning. The two fundamental systems of logic are propositional calculus and predicate calculus, although many extensions to these systems exist. Logic is used extensively in computer science and artificial intelligence. See also Axiom/Theorem, Rules of Inference.

Main Memory/Backup Memory
The part of the computer's circuitry which provides instructions and data to be fed into the central processor, and which stores the output of the latter's operation, is known as the main memory. By contrast, the backup memory, such as disc or tape, contains information in a form which can be transported from one machine to another.

A general philosophical view that only physical processes exist. The term is also applied to philosophical theories of mind which claim that mental states are identical with brain states. See also Dualism, Eliminativism, Functionalism.

A representation of some well-defined domain, such as Newtonian physics, such that there is a simple mapping between the rules and structures of the microworld and those of the domain.

A strategy to determine good moves in computer game playing by choosing the move that minimizes the loss the player can expect to incur, under the assumption that the player's opponent is adopting the same strategy (and hence trying to cause the maximum loss). The possible gain or loss for a sequence of moves is usually assessed using a static evaluation function applied to the state of play at the end of the sequence. See also Dynamic Value.

In vision, an internal description of the structure of an object, whether in terms of the structure of image features in a 2-dimensional image or solids in 3-dimensional space.

Naive Physics
People's commonsense knowledge about the behaviour of physical objects in the world -- for example, that a liquid spreads out when it pours onto a flat surface.

Neural Network
See Connectionist Model.

A single state in a state-space representation. In search, a junction point in the search tree, representing a state which may need to be considered either as a possible solution to a problem or en route to reaching such a solution.

Non-terminal Symbol
In a generative grammar, a non-terminal symbol labels a syntactic or lexical category, and is used in the formulation of the rules of the grammar. Examples of non-terminals are Prep, VP, Det, Pronoun, NP.

(a) A symbol to denote an operation, such as multiplication or comparison, which is applied to numbers or other data objects in a computer program.
(b) A discrete atomic mental operation that transforms one knowledge state, or state of working memory, into another. See also Problem Behaviour Graph.

Operator Schema
A knowledge representation formalism similar to a frame representing the type, preconditions, and actions of an operation. Used in artificial intelligence planning and problem solving systems.

Parallel Distributed Processing
Computing by means of a network of simple computational elements, working in parallel, each of which influences the other elements and is influenced by them. See also Connectionist Model, Sequential Processing.

A program which, given as input a grammar, a lexicon, and a word-string, will output, if the string is a well-formed sentence, a structural description of the sentence. Otherwise, the parser will reject the string. The structural description is often represented as a parse-tree, also called a phrase-marker, a diagrammatic representation of the sentence's constituent structure.

See Parser.

Pattern Matching
A programming method for matching a list of words (or other symbols) against a template, to discover whether particular words or combinations of words occur in the list. Pattern matching is built into POP-11. See also Wild Card.

See Competence/Performance.

Performance Knowledge
The knowledge posessed by a particular person which determines what or how they will perform on a given task See also Competence Knowledge.

A diagrammatic representation, in the form of an inverted schematic tree, of a sentence's constituent structure. See also Parser.

Phrase-Structure Rule
A rule which specifies the internal structure of a syntactic category. Rules are generally written in the following manner: X [IMAGE ] Y Z, where X, Y, and Z are syntactic category symbols, and Y and Z can replace X in its context within a sentence. A set of such phrase-structure rules, where at least one of the rules has the distinguished symbol on the left-hand side of the arrow, constitutes a phrase-structure grammar.

A tiny patch of an image. Images are normally broken down into a rectangular lattice of square pixels like tiles on a wall, although hexagonal tessellations have also been used.

A routinized program for behaviour that is triggered when certain specific environmenal conditions are satisfied.

The selection of a sequence of operations in order to bring about one or more goals. An important area of enquiry of artificial intelligence. See also Problem Behaviour Graph, Problem Reduction.

See Arc/Link/Pointer.

A programming language for artificial intelligence teaching and research.

Those aspects of the study of language that pertain to the identity and intentions of the speaker and hearer, and the context in which speech takes place. The context is sometimes most narrowly regarded as the body of world knowledge to which speakers and hearers have access in generating and interpreting speech. Pragmatics belongs to the study of linguistic performance. See also semantics, speech act, syntax.

In logic, a function whose value is is either `true', or `false'. It specifies a relatioship between arguments. See also Axiom/Theorem, Formula.

Predicate Calculus/Predicate Logic
A system of logic in which one can formalize inferences by representing relationships between predicates such as `...is happy' and `...is wise'. Predicate calculus incorporates, but extends, propositional calculus. See also Axiom/Theorem, Logic, Quantifier/Quantification.

Problem Behaviour Graph
A schematic representation of a subject's problem space, in the form of labeled boxes denoting knowledge states, and directed links representing the mental operations that transform each such state into a new state. See also Knowledge Representation, Planning.

Problem Reduction
A method of solving problems by splitting them into more manageable parts.

Problem Space
A set of knowledge states, including a start-start and a goal-state, and a set of admissible problem-specific operations which can be performed on these states. The problem space can be represented schematically by a problem behaviour graph.

See Declarative/Procedural.

Procedural Programming Language
A programming language such as POP-11 consisting procedure definitions together with sequences of commands for invoking them.

A sequence of instructions in a programming language designed to carry out a coherent operation or set of operations. Procedures often operate on data, passed to them through arguments, and return results, which may be used by other parts of the program. Procedures are first defined, to establish the actions they take, then called to carry out those actions.

Production System
A knowledge representation formalism consisting of collections of condition-action rules (called production rules), a database which is modified in accordance with the rules, and a production system interpreter which controls the operation of the rules. See also Conflict Resolution Strategy.

Production System Interpreter
The `control mechanism' of a production system, determining the order in which production rules are fired.

A set of abstract instructions or procedures for a computer to perform. When the instuctions are written in a high-level language like POP-11, they have to be converted, either by compilation or interpretation, into basic operations that the computer can perform. See also Algorithm, Hardware, Software.

A programming language with a strongly declarative style, which is based on predicate calculus. See also Resolution.

See Attribute/Feature/Property.

Property Inheritance
A process by which features attached to parent nodes (more general concepts or inclusive classes) in an isa hierarchy are passed down to (`inherited by') their children (more specific concepts or sub-classes) in such cases where no properties or attributes of the same type are associated explicitly with the children nodes. For example, if we know that birds can fly and that canaries are birds, then we can infer that canaries too can fly.

Propositional Calculus
A simple but powerful system of logic for representing implications between logically compound sentences, such as `either A or not B', `if B then A', etc. The system will prove, for example, that each of these two sentences implies the other. See also Predicate Calculus/Predicate Logic, Rules of Inference.

Protocol Analysis
A method of studying subjects' mental processes in the performance of tasks by recording their spontaneous `thinking aloud' and subsequently segmenting the running commentary into the discrete atomic mental operations that the subjects have used in the accomplishment of the tasks. See also Operator, Problem Space.

Quantifiers play an important role in predicate calculus logic. There are two kinds of quantifier: the universal quantifier (as in `all dogs are mammals') and the singular or existential quantifier (as in `some mammals are dogs').

Self-reference, particularly in the form of a procedure containing, within its body, a call to iteslf. A recursive phrase-structure rule is one in which the symbol on the left-hand side of the arrow also appears on the right-hand side -- for example, NP [IMAGE ] NP Prep NP, which says that a noun-phrase can be made up of two embedded noun-phrases joined by a preposition.

An area of an image which is homogeneous in intensity or texture.

Region Map
A 2-D array representing a segmentation of an input image into regions. The array is typically the same size as the input image, so that there is a one-to-one correspondence between array cells and image pixels. Array cells belonging to the same region contain a label which is unique to that region.

Repair Heuristic
A general-purpose heuristic used to effect a repair.

Repair Theory
An analysis of errors, based on the assumption that a learner who reaches as impasse, as a result of following a wrong method, will devise a repair to be able to continue solving the problem.

Repeat Loop
A structure in a program which allows an instruction, or a sequence of instructions, to be carried out repeatedly. The repetition may continue indefinitely, or for a fixed number of times, or may end when some condition specified in the program becomes true. See also Until Loop, While Loop.

A popular technique used in automated theorem proving systems. A version of resolution underlies the logic programming language Prolog.

Restriction Procedure
Matching of variables in lists can be constrained, in POP-11, by a restriction procedure, which specifies some property or feature a variable must have.

See Argument/Result, Input/Output.

The node of a search tree from which all other nodes can be reached by moving down the branches. Often represents the starting state of a problem or game.

Rule Body
The `action' part of a production rule, which specifies what actions are to be performed if the rule is fired (i.e., there is a successful match of the rule head against the contents of the working memory). Most typically, these are actions which change the contents of the working memory by adding and removing facts. See also Conflict Resolution Strategy, Production System.

Rule Head
The `condition' part of a production rule (in the POP-11 production system formalism, the first line of a production rule) consisting of one or more facts which the production system interpreter attempts to match against the contents of the working memory. See also Conflict Resolution Strategy, Rule Body.

Rule-by-Rule Principle
Maintains that the meaning of a sentence can be compositionally built up by semantic rules in tandem with the syntactic parse. See also Formal Semantics.

The set of rules in a production system. See also Rule Body, Rule Head.

Rules of Inference
Any system of logical deduction uses general rules of inference to allow logical formulae to be derived from others. For instance, a rule of inference in many systems of propositional calculus is modus ponens, which, given the propositions `if P then Q' and `P', allows one to infer `Q'.

A structure rather like a frame which represents situations or events, and which is used as a knowledge representation formalism. It is particularly suited to natural language understanding systems. See also Conceptual Primitive.

A technique of problem solving in which possible solutions are explored in a systematic way, in effect by asking a series of ``What if ...?'' questions. Asking each a question corresponds to trying out a possible state of the domain in which the program operates to see if it leads to a solution of the problem.

Search Strategy
Any way of organizing the questions asked in problem solving by search, so as either to find a solution as rapidly as possible or to find a particularly good solution when more than one solution is possible.

Search Tree
The exploration of possibilities in problem solving by search generally leads to a branching structure, in which each state may give rise to a new set of states (sometimes called successor states) and each of these may give rise to successor states of its own, and so on. This structure is not usually represented in full in computer memory, but is implicit in the problem itself. Finding a solution involves systematically traversing this tree.

Semantic Network
A knowledge representation formalism which describes objects and their relationships in terms of a network consisting of labelled arcs and nodes.

Semantic Value
In formal semantics, the semantic value of an expression is the individual(s) or state(s) in the world to which the expression refers, or which make that expression true.

The study of meaning in language. See also formal semantics, pragmatics, syntax.

Sequential Processing
A computer architecture in which a central processor carries out a series of operations in sequence. See also Computation, Parallel Distributed Processing.

Set-Value Variable
In POP-11 a set-value variable in a pattern matches an equivalent element in the list being matched. If there is a correct match, then the item in the list is assigned to the variable. See also Use-Value Variable, Wild Card.

An element in a frame, which can be filled with a value. For instance a `chair' frame may have a `number of legs' slot, perhaps filled with the default value of 4.

A program for a computer, together with the data upon which the program operates. See also algorithm, hardware.

Speech Act
The theory of speech acts views natural language utterances as actions -- for example, questions, orders, statements -- on the part of speakers. Speech act theory belongs to the field of pragmatics.

A description of a possible arrangement of a domain. For instance, in game playing, a state may correspond to a position of pieces on the board; in route finding, a state may correspond to arrival at a specified place at a specified time; in planning, a state may correspond to an arrangement in space of some objects to be manipulated.

The set of all the states which could possibly need to be considered in the course of solving a particular problem.

Static Evaluation Function
In computer game playing, any method of determining the advantage to the player of a given state of play, without looking ahead at possible future moves.

Structural Description
A description of the formal constituents, features, and relationships that exhaustively account for the structural integrity and cohesion of an object. A structural description of, for example, an arch will include such terms as `block', `supported by', and `abutting'. See also Knowledge Representation, Semantic Network.

In a program such as ELIZA, using part of the user's input sentence to produce response. In general, replacing part of a string of words or other symbols by different symbols, depending on context.

Successive Refinement
A method of software design characteristic of artificial intelligence program development, which involves starting with a relatively crude working program and gradually increasing its complexity and sophistication.

Syntactic Category
A grammatical class determined on the basis of the syntactic role it fills in the construction of sentences, used in the formal description of language. It is labelled by a category symbol, such as NP, VP, PrepP. See also Phrase-Structure Rule, Syntax.

Syntactically Well-Formed
See Grammatical.

(a) In programming, the rules by which the words in a program are combined to form commands to a computer.
(b) For natural languages, the study of the rules governing the way in which words and phrases are combined to form sentences in a language. The word is also sometimes used to refer to the rules themselves; thus one may speak of `English syntax', `the syntax of German', and so on, to mean much the same thing as `English grammar', `the grammar of German', and so forth. See also Grammar.

Taxonomic Tree
See isa Hierarchy.

In vision, a stored sub-image with which to compare incoming images.

Terminal Symbol
Terminal symbols are the output of the syntactic component of a grammar, and are usually identified with the words and grammatically meaningful sub-parts (`morphemes') of words. In a phrase-structure grammar, they will only ever appear on the right-hand side of lexical rules. See Lexical Category, Lexicon, Phrase-Structure Rule, Syntax.

See Axiom/Theorem.

A relationship which, for any relation R, if xRy and yRz, then xRz. For example, if a canary is a bird and a bird is an animal, then a canary is an animal.

A production rule is said to be triggered if there is a successful match of the rule head against the facts in working memory. See also Conflict Resolution Strategy, Production System.

The assumption that meaning can be defined in terms of the conditions in the real world under which a sentence may be used to make a true statement. See also Formal Semantics.

Turing Test
A hypothetical test for computer intelligence, proposed by Alan Turing in 1950, involving a computer program generating a conversation which could not be distinguished from that of a real human.

Until Loop
A structure in a computer program which allows a sequence of instructions to be repeated until some condition becomes true. See also Repeat Loop, While Loop.

Use-Value Variable
In POP-11 when a use-value variable occurs in a list, the value of the variable is inserted at that place in the list. See also Set-Value Variable, Wild Card.

See Built-In/User-Defined.

The actual data which have been stored in a section of computer memory and which are associated with a variable. The value can change as new assignments to the variable are made.

In many programming languages, there is a class of terms which do not have a fixed value, but to which values can be assigned. These are called variables. Constants, on the other hand, are terms whose values are fixed. See also Local/Global.

Visual Display Unit (VDU)
A screen, usually like a TV set, that displays text or pictures representing the output of a program while it is running on a computer. See also Hardware, Input/Output.

von Neumann Architecture
The `classic' design for computer hardware, named afer the mathematician John von Neumann, who formulated the main elements of the standard, sequential, stored program, computer architecture in the late 1940s. Non-von Neumann architectures are now being developed that exploit various forms of parallel or distributed processing. See also central processor, computation, connectionist model, parallel distributed processing.

While Loop
A structure in a computer program that allows a sequence of instructions to be repeated while some condition remains true. See also Repeat Loop, Until Loop.

Wild Card
In pattern matching, an element in a pattern which can match any element in the equivalent section of the list being matched. See also Set-Value Variable, Use-Value Variable.

A particular kind of data object. In POP-11, a word identified by sequences of symbols within double quotation marks, such as "fred", "abc123". Each word used by a program is stored in an internal dictionary.

Word Concept
The stored mental representation of a word.

Working Memory
Sometimes also called `short term memory' by psychologists, it is a mental workspace consisting of a small set of data items representing the current state of knowledge of a system at any stage in the performance of a task, and which is transformed into a new set, in humans by the application of a discrete mental operation (operator), and in production systems on the firing of a new production rule. See also Production System.

[Next] [Up]
Next: About this document Up: Content

Cogsweb Project: luisgh@cogs.susx.ac.uk