The types of list structures represent clauses in propositional or predicate logic such as (or ~(MARRIED ?x ?y) ~(DAUGHTER ?z ?y) (MOTHER ?y ?z)) or rules such as (and ((cloudy-sky) (low-bar-pressure) (high-humidity)) (conclude (rain likely)) or fragments of associative networks in below Fig

**Structures used in Matching**

The types of list structures represent clauses in
propositional or predicate logic such as (or ~(MARRIED ?x ?y) ~(DAUGHTER ?z ?y)
(MOTHER ?y ?z)) or rules such as (and ((cloudy-sky) (low-bar-pressure)
(high-humidity)) (conclude (rain likely)) or fragments of associative networks
in below Fig

The other common structures include strings of
characters a_{1} a_{2 . . .} a_{k} , where the a_{i}
belong to given alphabet A, vector X = (x_{1} x_{2 . . .} x_{n}),
where the x_{i} represents attribute values, matrices M (rows of
vectors), general graphs, trees and sets

Variables

The structures are constructed from basic atomic
elements, numbers and characters

Character string elements may represent either
constants or variables

If variables, they may be classified by either the
type of match permitted or their value domains

An open variable can be replaced by a single item

Segment variable can be replaced by zero or more
items

Open variable are replaced with a preceding
question mark (?x. ?y, ?class)

They may match or assume the value of any single
string element or word, but they are subject to consistency constraints

For example, to be consistent, the variable ?x can
be bound only to the same top level element in any single structure

Thus (a ?x d ?x e) may match (a b d b e), but not
(a b d a e)

Segment variable types will be preceded with an
asterisk (*x, *z, *words)

This type of variable can match an arbitrary number
or segment of contiguous atomic elements

For example, (* x d (e g) *y) will match the
patterns

(a (b c) d (e f) g h), (d (e f ) (g))

Subject variable may also be subject to consistency
constraints similar to open variables

Nominal variables

Qualitative variables whose values or states have
no order nor rank

It is possible to distinguish between equality or
inequality between two objects

Each state can be given a numerical code

For example, “marital status” has states of
married, single, divorced or widowed. These states could be assigned numerical
codes, such as married = 1, single = 2, divorced = 3 and widowed = 4

Ordinal variables

Qualitative variables whose states can be arranged
in a rank order

It may be assigned numerical values

Foe example, the states very tall, tall, medium,
short and very short can be arranged in order from tallest to shortest and can
be assigned an arbitrary scale of 5 to 1

Binary variable

Qualitative discrete variables which may assume
only one of two values, such as 0 or 1, good or bad, yes or no, high or low

Interval variables or Metric variables

Qualitative variables which take on numeric values
and for which equal differences between values have the same significance

For example, real numbers corresponding to
temperature or integers corresponding to an amount of money are considered as
interval variables

Graphs and Trees

A graph is a collection of points called vertices,
some of which are connected by line segments called edges

Graphs are used to model a wide variety of
real-life applications, including transportation and communication networks,
project scheduling, and games

A graph G = (V, E) is an ordered pair of sets V and
E. the elements V are nodes or vertices and the elements of E are a subset of V
X V called edges

An edge joints two distinct vertices in V

Directed graphs or digraphs, have directed edges or
arcs with arrows

If an arc is directed from node n_{i} to n_{j}
, node n_{i} is said to be a parent or successor of n_{j} and n_{j}
is the child or successor of n_{i}

Undirected graphs have simple edges without arrows
connecting the nodes

A path is a sequence of edges connecting two modes
where the endpoint of one edge is the start of its successor

A cycle is a path in which the two end points
coincide

A Connected graph is a graph for which every pair
of vertices is joined by a path

A graph is complete if every element of V X V is an
edge

A tree is a connected graph in which there are no
cycles and each node has at most one parent below

A node with no parent is called root node

A node with no children is called leaf node

The depth of the root node is defined as zero

The depth of any other node is defined to be the
depth of its parent plus 1

Sets and Bags

A set is represented as an unordered list of unique
elements such as the set (a d f c) or (red blue green yellow)

A bag is a set which may contain more than one copy
of the same member a, b, d and e

Sets and bags are structures used in matching
operations

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Artificial Intelligence : Structures used in Matching |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.