Theory of computation: Abbreviations

• DFA

• DPDA-I

• DPDA-II

• DTM

• FSM

• LBA

• MTM

• MDTM

• NFA

• NPDA-I

• NPDA-II

• NTM

• PTM

AT

Automata Theory

CF

Context-free, usually related to a grammar, as in context-free grammar.

CL

Classical logic

CS

1. Computer Science

2. 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