List of Mathematical Terms used in theory of computation

Alphabet – A finite set of objects
Argument – An input to a function

Binary relation – A relation with domain as set of pairs
Boolean operation – Operation on bolean values
Boolean value – TRUE or FALSE (1 or 0)

Cartesian product – An operation on sets forming a set of all tuples of elements from respective sets
Complement – An operation on a set, forming the set of all non-existent elements
Concatenation – Joining of strings of one set with that of another
Conjunction – Boolean AND operation
Connected graph – A graph with paths that connect every two nodes
Cycle – A path that starts and ends in the same node

Directed graph – A collection of points and arrows that connect some pairs of points
Disjunction – Boolean OR operation
Domain – Set of possible inputs to a function

Edge – A line in a graph
Element – An object in a set
Empty set – Set without any member
Empty string – Zero length string
Equivalence relation – A binary relation that is reflective, symmetric and transitive

Function – An operation that converts inputs into outputs
Graph – A collection of points and lines that connect some pairs of points

Intersection – An operation on sets to form a set of common elements
k-tuple – A list of k objects
Language – Set of strings
Member – An element in a set
Node – A point in a graph

Pair – A list of two elements
Path – Sequence of nodes in a graph connected by edges
Predicate – A function whose range is {TRUE, FALSE}
Property – A predicate
Range – The set from which outputs of a function are drawn
Relation – A predicate, most typically when the domain is a set of k-tuples

Sequence – List of objects
Set – Group of objects
Simple path – A path without repetition
String – List of symbols representing alphabets
Symbol – An alphabet

Tree – A connected graph without simple cycles
2-Tuple – List of two elements

Union – An operation on sets to combine the elements into a single set
Vertex – A point in a graph

Related Articles

Terms in Computer Architecture