Second-Order Logic over Finite Structures – Report on a Research Programme
Identifieur interne : 006B33 ( Main/Exploration ); précédent : 006B32; suivant : 006B34Second-Order Logic over Finite Structures – Report on a Research Programme
Auteurs : Georg Gottlob [Autriche]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: This paper reports about the results achieved so far in the context of a research programme at the cutting point of logic, formal language theory, and complexity theory. The aim of this research programme is to classify the complexity of evaluating formulas from different prefix classes of second-order logic over different types of finite structures, such as strings, graphs, or arbitrary structures. In particular, we report on classifications of second-order logic on strings and of existential second-order logic on graphs.
Url:
DOI: 10.1007/978-3-540-25984-8_16
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002299
- to stream Istex, to step Curation: 002268
- to stream Istex, to step Checkpoint: 001742
- to stream Main, to step Merge: 006E37
- to stream Main, to step Curation: 006B33
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Second-Order Logic over Finite Structures – Report on a Research Programme</title><author><name sortKey="Gottlob, Georg" sort="Gottlob, Georg" uniqKey="Gottlob G" first="Georg" last="Gottlob">Georg Gottlob</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:959C346C4BEC0856416C1648C45906C5377CB885</idno><date when="2004" year="2004">2004</date><idno type="doi">10.1007/978-3-540-25984-8_16</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-076LZMFH-M/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002299</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002299</idno><idno type="wicri:Area/Istex/Curation">002268</idno><idno type="wicri:Area/Istex/Checkpoint">001742</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001742</idno><idno type="wicri:doubleKey">0302-9743:2004:Gottlob G:second:order:logic</idno><idno type="wicri:Area/Main/Merge">006E37</idno><idno type="wicri:Area/Main/Curation">006B33</idno><idno type="wicri:Area/Main/Exploration">006B33</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Second-Order Logic over Finite Structures – Report on a Research Programme</title><author><name sortKey="Gottlob, Georg" sort="Gottlob, Georg" uniqKey="Gottlob G" first="Georg" last="Gottlob">Georg Gottlob</name><affiliation wicri:level="3"><country xml:lang="fr">Autriche</country><wicri:regionArea>Institut für Informationssysteme, Technische Universität Wien, Favoritenstraße 9-11, A-1040, Wien</wicri:regionArea><placeName><settlement type="city">Vienne (Autriche)</settlement><region nuts="2" type="province">Vienne (Autriche)</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Autriche</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: This paper reports about the results achieved so far in the context of a research programme at the cutting point of logic, formal language theory, and complexity theory. The aim of this research programme is to classify the complexity of evaluating formulas from different prefix classes of second-order logic over different types of finite structures, such as strings, graphs, or arbitrary structures. In particular, we report on classifications of second-order logic on strings and of existential second-order logic on graphs.</div></front></TEI><affiliations><list><country><li>Autriche</li></country><region><li>Vienne (Autriche)</li></region><settlement><li>Vienne (Autriche)</li></settlement></list><tree><country name="Autriche"><region name="Vienne (Autriche)"><name sortKey="Gottlob, Georg" sort="Gottlob, Georg" uniqKey="Gottlob G" first="Georg" last="Gottlob">Georg Gottlob</name></region><name sortKey="Gottlob, Georg" sort="Gottlob, Georg" uniqKey="Gottlob G" first="Georg" last="Gottlob">Georg Gottlob</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006B33 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006B33 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:959C346C4BEC0856416C1648C45906C5377CB885
|texte= Second-Order Logic over Finite Structures – Report on a Research Programme
}}
| This area was generated with Dilib version V0.6.33. |  |