Second-Order Logic over Finite Structures – Report on a Research Programme
Identifieur interne : 002268 ( Istex/Curation ); précédent : 002267; suivant : 002269Second-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
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :002299
Links to Exploration step
ISTEX:959C346C4BEC0856416C1648C45906C5377CB885Le 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><affiliation wicri:level="1"><mods:affiliation>Institut für Informationssysteme, Technische Universität Wien, Favoritenstraße 9-11, A-1040, Wien, Austria</mods:affiliation><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></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: gottlob@dbai.tuwien.ac.at</mods:affiliation><country wicri:rule="url">Autriche</country></affiliation></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></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="1"><mods:affiliation>Institut für Informationssysteme, Technische Universität Wien, Favoritenstraße 9-11, A-1040, Wien, Austria</mods:affiliation><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></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: gottlob@dbai.tuwien.ac.at</mods:affiliation><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></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002268 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 002268 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Curation
|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. |  |