Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Free
Faster access than browser!
 
New! Save your pages! » Create account

Linear bounded automaton

+ Save concept Saved concepts

In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine. [1]

17 relations: Alphabet (formal languages), Computational complexity theory, Computer, Computer science, Context-sensitive language, DSPACE, Finite set, Formal grammar, Immerman–Szelepcsényi theorem, Information and Computation, John Myhill, Linear function, Linear speedup theorem, Non-deterministic Turing machine, NSPACE, S.-Y. Kuroda, Turing machine.

Alphabet (formal languages)

In formal language theory, a non-empty set is called alphabet when its intended use in string operations shall be indicated.

New!!: Linear bounded automaton and Alphabet (formal languages) · See more »

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: Linear bounded automaton and Computational complexity theory · See more »

Computer

A computer is a general-purpose device that can be programmed to carry out a set of arithmetic or logical operations automatically.

New!!: Linear bounded automaton and Computer · See more »

Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations Computer science is the scientific and practical approach to computation and its applications.

New!!: Linear bounded automaton and Computer science · See more »

Context-sensitive language

In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar (and equivalently by a noncontracting grammar).

New!!: Linear bounded automaton and Context-sensitive language · See more »

DSPACE

In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine.

New!!: Linear bounded automaton and DSPACE · See more »

Finite set

In mathematics, a finite set is a set that has a finite number of elements.

New!!: Linear bounded automaton and Finite set · See more »

Formal grammar

In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) is a set of production rules for strings in a formal language.

New!!: Linear bounded automaton and Formal grammar · See more »

Immerman–Szelepcsényi theorem

In computational complexity theory, the Immerman–Szelepcsényi theorem was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize.

New!!: Linear bounded automaton and Immerman–Szelepcsényi theorem · See more »

Information and Computation

Information and Computation is a computer science journal published by Elsevier (formerly Academic Press).

New!!: Linear bounded automaton and Information and Computation · See more »

John Myhill

John R. Myhill, Sr. (11 August 1923 – 15 February 1987) was a British mathematician.

New!!: Linear bounded automaton and John Myhill · See more »

Linear function

In mathematics, the term linear function refers to two distinct, although related, notions.

New!!: Linear bounded automaton and Linear function · See more »

Linear speedup theorem

In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any Turing machine solving a problem in time f(n), there is another machine that solves the same problem in time at most cf(n) + n + 2.

New!!: Linear bounded automaton and Linear speedup theorem · See more »

Non-deterministic Turing machine

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers.

New!!: Linear bounded automaton and Non-deterministic Turing machine · See more »

NSPACE

In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine.

New!!: Linear bounded automaton and NSPACE · See more »

S.-Y. Kuroda

, aka S.-Y. Kuroda, was Professor Emeritus and Research Professor of Linguistics at the University of California, San Diego.

New!!: Linear bounded automaton and S.-Y. Kuroda · See more »

Turing machine

A Turing machine is an abstract "machine" that manipulates symbols on a strip of tape according to a table of rules; to be more exact, it is a mathematical model that defines such a device.

New!!: Linear bounded automaton and Turing machine · See more »

Redirects here:

LBA compete, LBA-compete, Linear bounded automata.

References

[1] https://en.wikipedia.org/wiki/Linear_bounded_automaton

OutgoingIncoming
Hey! We are on Facebook now! »