Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Descriptive complexity theory (view)

searching for Descriptive Complexity 22 found (56 total)

Samson Abramsky (1,187 words) [view diff] case mismatch in snippet view article find links to article

categorical semantics to finite model theory, with applications to descriptive complexity. Abramsky was educated at Hasmonean Grammar School for Boys, Hendon

PSPACE (982 words) [view diff] case mismatch in snippet view article find links to article

called APTIME or just AP. A logical characterization of PSPACE from descriptive complexity theory is that it is the set of problems expressible in second-order

Elementary recursive function (1,025 words) [view diff] case mismatch in snippet view article find links to article

n ∧ m {\displaystyle n\wedge m} is a bitwise AND of n and m. In descriptive complexity, ELEMENTARY is equal to the class HO of languages that can be described

Logic of graphs (5,029 words) [view diff] case mismatch in snippet view article find links to article

values range from 0 to the number of vertices, have been used in descriptive complexity in an attempt to provide a logical description of decision problems

Two-variable logic (384 words) [view diff] case mismatch in snippet view article find links to article

Logic in Computer Science, 1997. Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.

NEXPTIME (1,066 words) [view diff] case mismatch in snippet view article find links to article

only if there exist sparse languages in NP that are not in P. In descriptive complexity, the sets of natural numbers that can be recognized in NEXPTIME

Blum–Shub–Smale machine (654 words) [view diff] exact match in snippet view article find links to article

ISBN 3-540-66752-0. Zbl 0948.68082. Grädel, E. (2007). "Finite Model Theory and Descriptive Complexity". Finite Model Theory and Its Applications (PDF). Springer-Verlag

Colour refinement algorithm (899 words) [view diff] case mismatch in snippet view article find links to article

1979.8. Retrieved 2024-01-18. Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.

Universal probability bound (901 words) [view diff] case mismatch in snippet view article find links to article

multi-billion year history." The rank complexity is Dembski's φ function which ranks patterns in order of their descriptive complexity. See specified complexity.

Modal μ-calculus (1,816 words) [view diff] exact match in snippet view article find links to article

Emerson, E. Allen (1996). "Model Checking and the Mu-calculus". Descriptive Complexity and Finite Models. American Mathematical Society. pp. 185–214. ISBN 0-8218-0517-7

Complexity (4,498 words) [view diff] case mismatch in snippet view article find links to article

algorithmic information theory, the Kolmogorov complexity (also called descriptive complexity, algorithmic complexity or algorithmic entropy) of a string is the

Second-order logic (4,502 words) [view diff] case mismatch in snippet view article find links to article

intimately tied to computational complexity theory. The field of descriptive complexity studies which computational complexity classes can be characterized

Statistical inference (5,519 words) [view diff] case mismatch in snippet view article find links to article

average and asymptotically. In minimizing description length (or descriptive complexity), MDL estimation is similar to maximum likelihood estimation and

Specified complexity (3,965 words) [view diff] case mismatch in snippet view article find links to article

that is, all the opportunities to bring about an event of T's descriptive complexity and improbability by multiple agents witnessing multiple events

Query complexity (244 words) [view diff] case mismatch in snippet view article find links to article

size Query (complexity), a mapping between logical structures in descriptive complexity This set index article includes a list of related items that share

P versus NP problem (7,784 words) [view diff] case mismatch in snippet view article find links to article

as certain classes of logical statements, as a result of work in descriptive complexity. Consider all languages of finite structures with a fixed signature

Courcelle's theorem (3,146 words) [view diff] case mismatch in snippet view article find links to article

2014. Grohe, Martin; Mariño, Julian (1999), "Definability and descriptive complexity on databases of bounded tree-width", Database Theory — ICDT'99:

History of logic (13,249 words) [view diff] case mismatch in snippet view article find links to article

characterized in logical terms as a result of investigations into descriptive complexity. Model theory applies the methods of mathematical logic to study

Paris Kanellakis (3,747 words) [view diff] exact match in snippet view article find links to article

1016/S0304-3975(96)00194-6. Immerman, Neil; Kolaitis, Phokion, eds. (1997). Descriptive Complexity and Finite Models. American Mathematical Society. ISBN 9780821870761

List of multiple discoveries (11,335 words) [view diff] case mismatch in snippet view article find links to article

Kolmogorov complexity, also known as "Kolmogorov–Chaitin complexity", descriptive complexity, etc., of an object such as a piece of text is a measure of the

Alexei Semenov (mathematician) (3,342 words) [view diff] case mismatch in snippet view article

solved a problem of Andrey Kolmogorov from his work originated descriptive complexity theory. He also contributed to the foundations of the theory of

Dependence logic (4,538 words) [view diff] case mismatch in snippet view article find links to article

with a certain majority quantifier, the latter leading to a new descriptive complexity characterization of the counting hierarchy. Game semantics Branching