Matches in DBpedia 2014 for { <http://dbpedia.org/resource/FO_(complexity)> ?p ?o. }
Showing items 1 to 24 of
24
with 100 items per page.
- FO_(complexity) abstract "In descriptive complexity, a branch of computational complexity, FO is a complexity class of structures which can be recognized by formulas of first-order logic. It is the foundation of the field of descriptive complexity and is equal to the complexity class AC0. Descriptive complexity uses the formalism of first-order logic, but does not use most of the usual notions associated to logic as proof theory or axiomatization.When the predicates are restricted to a set X, FO[X] correspond to some other class, and there exists specific sets X such FO[X] has some interesting properties. In particular, FO[<] is equal to the set of star-free languages. Having two different definitions, in term of logic and in term of regular expression, suggests that this class may have some mathematical interest, and that we may use together methods for both domain to do proofs.Similarly, various extensions of FO, formed by the addition of certain operators, give rise to other well-known complexity classes, allowing the complexity of some problems to be proven without having to look at them as algorithm problem.".
- FO_(complexity) wikiPageExternalLink genspec.pdf.
- FO_(complexity) wikiPageExternalLink tcs93.pdf.
- FO_(complexity) wikiPageExternalLink descriptive_complexity.html.
- FO_(complexity) wikiPageExternalLink capture.pdf.
- FO_(complexity) wikiPageID "7400401".
- FO_(complexity) wikiPageRevisionID "602796008".
- FO_(complexity) hasPhotoCollection FO_(complexity).
- FO_(complexity) subject Category:Complexity_classes.
- FO_(complexity) subject Category:Descriptive_complexity.
- FO_(complexity) subject Category:Finite_model_theory.
- FO_(complexity) type Abstraction100002137.
- FO_(complexity) type Class107997703.
- FO_(complexity) type Collection107951464.
- FO_(complexity) type ComplexityClasses.
- FO_(complexity) type Group100031264.
- FO_(complexity) comment "In descriptive complexity, a branch of computational complexity, FO is a complexity class of structures which can be recognized by formulas of first-order logic. It is the foundation of the field of descriptive complexity and is equal to the complexity class AC0.".
- FO_(complexity) label "FO (complexity)".
- FO_(complexity) sameAs m.0260k93.
- FO_(complexity) sameAs Q5426969.
- FO_(complexity) sameAs Q5426969.
- FO_(complexity) sameAs FO_(complexity).
- FO_(complexity) wasDerivedFrom FO_(complexity)?oldid=602796008.
- FO_(complexity) isPrimaryTopicOf FO_(complexity).