Ehrenfeucht-Fraïssé Games on Random Structures (Q3638295)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Ehrenfeucht-Fraïssé Games on Random Structures	scientific article

Statements

scholarly article

0 references

Ehrenfeucht-Fraïssé Games on Random Structures (English)

0 references

Benjamin Rossman

0 references

Logic, Language, Information and Computation

0 references

publication date

2 July 2009

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/978-3-642-02261-6_28

0 references

\(\Sigma_ 1^ 1\)-formulae on finite structures

0 references

A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log <i>n</i> Negation Gates

0 references

Lower bounds for recognizing small cliques on CRCW PRAM's

0 references

The average sensitivity of bounded-depth circuits

0 references

Definability by constant-depth polynomial-size circuits

0 references

Parity, circuits, and the polynomial-time hierarchy

0 references

A simple lower bound for monotone clique using a communication game

0 references

A logic for constant-depth circuits

0 references

Upper and lower bounds for first order expressibility

0 references

0 references

Number of variables is equivalent to space

0 references

Elements of finite model theory.

0 references

Constant depth circuits, Fourier transform, and learnability

0 references

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

0 references

0 references

Identifiers

zbMATH Open document ID

0 references

10.1007/978-3-642-02261-6_28

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:3638295

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q3638295&oldid=35116545"