en.unionpedia.org

State complexity, the Glossary

State complexity is an area of theoretical computer science dealing with the size of abstract automata, such as different kinds of finite automata.^[1]

35 relations: Alternating finite automaton, Ashok K. Chandra, Complementation of automata, Computational complexity theory, Conference on Implementation and Application of Automata, Dana Scott, Descriptional Complexity of Formal Systems, Deterministic finite automaton, Dexter Kozen, Finite-state machine, Giovanni Pighizzini, Immerman–Szelepcsényi theorem, John Shepherdson, Kai Salomaa, L (complexity), Landau's function, Larry Stockmeyer, Marek Chrobak, Michael O. Rabin, Michael Sipser, Moshe Vardi, NL (complexity), Nondeterministic finite automaton, Oleg Lupanov, P versus NP problem, Powerset construction, Regular language, Richard E. Ladner, Richard Lipton, Savitch's theorem, Self-verifying finite automaton, Theoretical computer science, Two-way finite automaton, Unambiguous finite automaton, Viliam Geffert.

Alternating finite automaton

In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential and universal transitions. State complexity and alternating finite automaton are finite automata.

See State complexity and Alternating finite automaton

Ashok K. Chandra

Ashok K. Chandra (30 July 1948 – 15 November 2014) was a computer scientist at Microsoft Research in Mountain View, California, United States, where he was a general manager at the Internet Services Research Center.

See State complexity and Ashok K. Chandra

Complementation of automata

In theoretical computer science and formal language theory, the complementation of an is the problem of computing an automaton that accepts precisely the words rejected by another automaton. Formally, given an automaton A which recognizes a regular language L, we want to compute an automaton that precisely recognizes the words that are not in L, i.e., the complement of L.

See State complexity and Complementation of automata

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other.

See State complexity and Computational complexity theory

Conference on Implementation and Application of Automata

CIAA, the International Conference on Implementation and Application of Automata is an annual academic conference in the field of computer science.

See State complexity and Conference on Implementation and Application of Automata

Dana Scott

Dana Stewart Scott (born October 11, 1932) is an American logician who is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California.

See State complexity and Dana Scott

Descriptional Complexity of Formal Systems

DCFS, the International Workshop on Descriptional Complexity of Formal Systems is an annual academic conference in the field of computer science.

See State complexity and Descriptional Complexity of Formal Systems

Deterministic finite automaton

In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. State complexity and deterministic finite automaton are finite automata.

See State complexity and Deterministic finite automaton

Dexter Kozen

Dexter Campbell Kozen (born December 20, 1951) is an American theoretical computer scientist.

See State complexity and Dexter Kozen

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. State complexity and finite-state machine are finite automata.

See State complexity and Finite-state machine

Giovanni Pighizzini

Giovanni Pighizzini is an Italian theoretical computer scientist known for his work in formal language theory and particularly in state complexity of two-way finite automata.

See State complexity and Giovanni Pighizzini

Immerman–Szelepcsényi theorem

In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation.

See State complexity and Immerman–Szelepcsényi theorem

John Shepherdson

John Cedric Shepherdson, FBA (7 June 1926 – 8 January 2015) was a British logician who was Henry Overton Wills Professor of Mathematics at the University of Bristol from 1976 to 1991.

See State complexity and John Shepherdson

Kai Salomaa

Kai Tapani Salomaa (born 9 February 1960) is a Finnish Canadian theoretical computer scientist, known for his numerous contributions to the state complexity of finite automata.

See State complexity and Kai Salomaa

L (complexity)

In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space.

See State complexity and L (complexity)

Landau's function

In mathematics, Landau's function g(n), named after Edmund Landau, is defined for every natural number n to be the largest order of an element of the symmetric group Sn.

See State complexity and Landau's function

Larry Stockmeyer

Larry Joseph Stockmeyer (1948 – 31 July 2004) was an American computer scientist.

See State complexity and Larry Stockmeyer

Marek Chrobak

Marek Chrobak is a full professor at University of California, Riverside.

See State complexity and Marek Chrobak

Michael O. Rabin

Michael Oser Rabin (מִיכָאֵל עוזר רַבִּין; born September 1, 1931) is an Israeli mathematician, computer scientist, and recipient of the Turing Award.

See State complexity and Michael O. Rabin

Michael Sipser

Michael Fredric Sipser (born September 17, 1954) is an American theoretical computer scientist who has made early contributions to computational complexity theory.

See State complexity and Michael Sipser

Moshe Vardi

Moshe Ya'akov Vardi (משה יעקב ורדי) is an Israeli mathematician and computer scientist.

See State complexity and Moshe Vardi

NL (complexity)

In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.

See State complexity and NL (complexity)

Nondeterministic finite automaton

In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if. State complexity and Nondeterministic finite automaton are finite automata.

See State complexity and Nondeterministic finite automaton

Oleg Lupanov

Oleg Borisovich Lupanov (Оле́г Бори́сович Лупа́нов; 2 June 1932 – 3 May 2006) was a Soviet and Russian mathematician, dean of the Moscow State University's Faculty of Mechanics and Mathematics (1980–2006), head of the Chair of Discrete Mathematics of the Faculty of Mechanics and Mathematics (1981–2006).

See State complexity and Oleg Lupanov

P versus NP problem

The P versus NP problem is a major unsolved problem in theoretical computer science.

See State complexity and P versus NP problem

Powerset construction

In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language. State complexity and powerset construction are finite automata.

See State complexity and Powerset construction

Regular language

In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expression engines, which are augmented with features that allow the recognition of non-regular languages). State complexity and regular language are finite automata.

See State complexity and Regular language

Richard E. Ladner

Richard Emil Ladner is an American computer scientist known for his contributions to both theoretical computer science and assistive technology.

See State complexity and Richard E. Ladner

Richard Lipton

Richard Jay Lipton (born September 6, 1946) is an American computer scientist who is Associate Dean of Research, Professor, and the Frederick G. Storey Chair in Computing in the College of Computing at the Georgia Institute of Technology.

See State complexity and Richard Lipton

Savitch's theorem

In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity.

See State complexity and Savitch's theorem

Self-verifying finite automaton

In automata theory, a self-verifying finite automaton (SVFA) is a special kind of a nondeterministic finite automaton (NFA) with a symmetric kind of nondeterminism introduced by Hromkovič and Schnitger. State complexity and self-verifying finite automaton are finite automata.

See State complexity and Self-verifying finite automaton

References

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

State complexity, the Glossary

Table of Contents

References