Theory of computation: Abbreviations
AT
Automata Theory
CF
Context-free, usually related to a grammar, as in context-free grammar.
CL
Classical logic
CS
Computer Science
Context-sensitive, usually related to a grammar, as in context-sensitive grammar.
CT
Church's thesis
DFA
Deterministic Finite Automaton (DFA)
DPDA-I
Deterministic Push Down Automaton (DPDA-I) with 1 push-down store
DPDA-II
Deterministic Push Down Automaton (DPDA-II) with 2 push-down stores
DTM
Deterministic Turing Machine (DTM)
FSM
Finite State Machine
FOL
First-order logic
GF
Grammar Framework is a framework for working with natural languages.
HA
Heyting arithmetic
IL
Intuitionistic logic
IPL
Intuitionistic propositional logic
LBA
Linear Bounded Automaton (LBA)
MTM
Multitape Turing Machine (MTM)
MDTM
Multidimensional Turing Machine (MDTM)
NFA
Nondeterministic Finite Automaton (NFA)
NL
Natural language.
NPDA-I
Nondeterministic Push Down Automaton (NPDA-I) with 1 push-down store
NPDA-II
Nondeterministic Push Down Automaton (NPDA-II) with 2 push-down stores
NTM
Nondeterministic Turing Machine (NTM)
PA
Peano arithmetic
PDA
Push-down automata
PTM
Probabilistic Turing Machine (PTM)
TM
Turing Machine
TOC
Theory of Computation
UTM
Universal Turing Machine
Last updated