In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's theorem, which provides algorithms for evaluating monadic second-order formulas over graphs of bounded treewidth. It is also of fundamental importance in automata theory, where the Büchi-Elgot-Trakhtenbrot theorem gives a logical characterization of the regular languages.
| Attributes | Values |
|---|
| rdfs:label
| - Monadische Prädikatenlogik zweiter Stufe (de)
- Logique monadique du second ordre (fr)
- Monadic second-order logic (en)
|
| rdfs:comment
| - Die monadische Prädikatenlogik zweiter Stufe, nach dem englischen monadic second order logic auch kurz MSO genannt, ist ein Begriff aus dem Bereich der mathematischen Logik. Es handelt sich um dasjenige Fragment der Prädikatenlogik zweiter Stufe, das nur die einstelligen Prädikate betrachtet. (de)
- In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's theorem, which provides algorithms for evaluating monadic second-order formulas over graphs of bounded treewidth. It is also of fundamental importance in automata theory, where the Büchi-Elgot-Trakhtenbrot theorem gives a logical characterization of the regular languages. (en)
- En logique mathématique et en informatique théorique, la logique monadique du second ordre (abrégé en MSO pour monadic second order) est l'extension de la logique du premier ordre avec des variables dénotant des ensembles. De manière équivalente, c'est le fragment de la logique du second ordre où les quantifications du second ordre ne portent que sur des prédicats unaires (d'où le terme monadique), c'est-à-dire sur des ensembles. Par exemple : (fr)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - Die monadische Prädikatenlogik zweiter Stufe, nach dem englischen monadic second order logic auch kurz MSO genannt, ist ein Begriff aus dem Bereich der mathematischen Logik. Es handelt sich um dasjenige Fragment der Prädikatenlogik zweiter Stufe, das nur die einstelligen Prädikate betrachtet. (de)
- In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's theorem, which provides algorithms for evaluating monadic second-order formulas over graphs of bounded treewidth. It is also of fundamental importance in automata theory, where the Büchi-Elgot-Trakhtenbrot theorem gives a logical characterization of the regular languages. Second-order logic allows quantification over predicates. However, MSO is the fragment in which second-order quantification is limited to monadic predicates (predicates having a single argument). This is often described as quantification over "sets" because monadic predicates are equivalent in expressive power to sets (the set of elements for which the predicate is true). (en)
- En logique mathématique et en informatique théorique, la logique monadique du second ordre (abrégé en MSO pour monadic second order) est l'extension de la logique du premier ordre avec des variables dénotant des ensembles. De manière équivalente, c'est le fragment de la logique du second ordre où les quantifications du second ordre ne portent que sur des prédicats unaires (d'où le terme monadique), c'est-à-dire sur des ensembles. Par exemple :
* est une formule de MSO et elle se lit « il existe un ensemble Z tel qu'il existe un élément u qui appartient à Z et pour tout x, si x est dans Z, alors il existe y tel que y est fils de x et y est dans Z ». Ce n'est pas une formule de la logique du premier ordre car il y a une quantification du second ordre sur Z ;
* Toutes les formules de la logique du premier ordre sont des formules de MSO ;
* La formule n'est pas une formule de MSO car il y a une quantification sur un prédicat binaire R. Le problème de satisfiabilité de la logique du premier ordre étant indécidable, comme MSO est une extension conservatrice de la logique du premier ordre, le problème de satisfiabilité de MSO est aussi indécidable. Mais selon , MSO est une source de théories logiques à la fois expressives et décidables. (fr)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is Wikipage disambiguates
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)