Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Androidâ„¢ device!
Free
Faster access than browser!
 

Linear bounded automaton

+ Save concept

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

18 relations: Alphabet (formal languages), Computational complexity theory, Computer, Computer science, Context-sensitive language, DSPACE, Finite set, Finite-state machine, 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 string is defined as a finite sequence of members of an underlying base set; this set is called the alphabet of a string or collection of strings.

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 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 device that can be instructed to carry out sequences of arithmetic or logical operations automatically via computer programming.

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.

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

Context-sensitive language

In formal language theory, a context-sensitive language is a 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 »

Finite-state machine

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation.

New!!: Linear bounded automaton and Finite-state machine · 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 states that nondeterministic space complexity classes are closed under complementation.

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 but 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 a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

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! »