Volume

Dagstuhl Seminar Proceedings, Volume 6451

Publication Details

  • published at: 2007-04-23
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.06451.1
06451 Abstracts Collection – Circuits, Logic, and Games

Authors: Thomas Schwentick, Denis Thérien, and Heribert Vollmer

Abstract
From 08.11.06 to 10.11.06, the Dagstuhl Seminar 06451 ``Circuits, Logic, and Games'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Thomas Schwentick, Denis Thérien, and Heribert Vollmer. 06451 Abstracts Collection – Circuits, Logic, and Games. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{schwentick_et_al:DagSemProc.06451.1,
  author =	{Schwentick, Thomas and Th\'{e}rien, Denis and Vollmer, Heribert},
  title =	{{06451 Abstracts Collection – Circuits, Logic, and Games }},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6451},
  editor =	{Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.1},
  URN =		{urn:nbn:de:0030-drops-9785},
  doi =		{10.4230/DagSemProc.06451.1},
  annote =	{Keywords: Computational complexity theory, finite model theory, Boolean circuits, regular languages, finite monoids, Ehrenfeucht-Fra\backslash"\{\backslashi\}ss\backslash'\{e\} games}
}
Document
DOI: 10.4230/DagSemProc.06451.2
06451 Executive Summary – Circuits, Logic, and Games

Authors: Thomas Schwentick, Denis Thérien, and Heribert Vollmer

Abstract
In this document we describe the original motivation and goals of the seminar as well as the sequence of talks given during the seminar.
Cite as

Thomas Schwentick, Denis Thérien, and Heribert Vollmer. 06451 Executive Summary – Circuits, Logic, and Games. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{schwentick_et_al:DagSemProc.06451.2,
  author =	{Schwentick, Thomas and Th\'{e}rien, Denis and Vollmer, Heribert},
  title =	{{06451 Executive Summary – Circuits, Logic, and Games }},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6451},
  editor =	{Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.2},
  URN =		{urn:nbn:de:0030-drops-9774},
  doi =		{10.4230/DagSemProc.06451.2},
  annote =	{Keywords: Circuits, Logics, Games}
}
Document
DOI: 10.4230/DagSemProc.06451.3
A note on the size of Craig Interpolants

Authors: Uwe Schöning and Jacobo Torán

Abstract
Mundici considered the question of whether the interpolant of two propositional formulas of the form $F ightarrow G$ can always have a short circuit description, and showed that if this is the case then every problem in NP $cap$ co-NP would have polynomial size circuits. In this note we observe further consequences of the interpolant having short circuit descriptions, namely that UP $subseteq$ P$/$poly, and that every single valued NP function has a total extension in FP$/$poly. We also relate this question with other Complexity Theory assumptions.
Cite as

Uwe Schöning and Jacobo Torán. A note on the size of Craig Interpolants. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{schoning_et_al:DagSemProc.06451.3,
  author =	{Sch\"{o}ning, Uwe and Tor\'{a}n, Jacobo},
  title =	{{A note on the size of Craig Interpolants}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6451},
  editor =	{Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.3},
  URN =		{urn:nbn:de:0030-drops-9735},
  doi =		{10.4230/DagSemProc.06451.3},
  annote =	{Keywords: Interpolant, non-uniform complexity}
}
Document
DOI: 10.4230/DagSemProc.06451.4
Counting Results in Weak Formalisms

Authors: Arnaud Durand, Clemens Lautemann, and Malika More

Abstract
The counting ability of weak formalisms is of interest as a measure of their expressive power. The question was investigated in the 1980's in several papers in complexity theory and in weak arithmetic. In each case, the considered formalism (AC$^0$--circuits, first--order logic, $Delta_0$, respectively) was shown to be able to count precisely up to a polylogarithmic number. An essential part of each of the proofs is the construction of a 1--1 mapping from a small subset of ${0,ldots,N-1}$ into a small initial segment. In each case the expressibility of such a mapping depends on some strong argument (group theoretic device or prime number theorem) or intricate construction. We present a coding device based on a collision-free hashing technique, leading to a completely elementary proof for the polylog counting capability of first--order logic (with built--in arithmetic), $AC^0$--circuits, rudimentary arithmetic, the Linear Hierarchy, and monadic--second order logic with addition.
Cite as

Arnaud Durand, Clemens Lautemann, and Malika More. Counting Results in Weak Formalisms. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{durand_et_al:DagSemProc.06451.4,
  author =	{Durand, Arnaud and Lautemann, Clemens and More, Malika},
  title =	{{Counting Results in Weak Formalisms}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6451},
  editor =	{Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.4},
  URN =		{urn:nbn:de:0030-drops-9767},
  doi =		{10.4230/DagSemProc.06451.4},
  annote =	{Keywords: Small complexity classes, logic, polylog counting}
}
Document
DOI: 10.4230/DagSemProc.06451.5
Some Algebraic Problems with Connections to Circuit Complexity of Dynamic Data Structures

Authors: William Hesse

Abstract
While researching dynamic data structures of polynomial size that are updated by extremely simple circuits, we have come across many interesting algebraic problems. Some of these simple questions about small sums and products in an algebra would give lower bounds on the complexity of dynamic data structures.
Cite as

William Hesse. Some Algebraic Problems with Connections to Circuit Complexity of Dynamic Data Structures. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{hesse:DagSemProc.06451.5,
  author =	{Hesse, William},
  title =	{{Some Algebraic Problems with Connections to Circuit Complexity of Dynamic Data Structures}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6451},
  editor =	{Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.5},
  URN =		{urn:nbn:de:0030-drops-9749},
  doi =		{10.4230/DagSemProc.06451.5},
  annote =	{Keywords: Boolean Functions, auxiliary data, circuit complexity, lower bounds}
}
Document
DOI: 10.4230/DagSemProc.06451.6
Structure Theorem and Strict Alternation Hierarchy for FO² on Words

Authors: Philipp Weis and Neil Immerman

Abstract
It is well-known that every first-order property on words is expressible using at most three variables. The subclass of properties expressible with only two variables is also quite interesting and well-studied. We prove precise structure theorems that characterize the exact expressive power of first-order logic with two variables on words. Our results apply to FO$^2[<]$ and FO$^2[<,suc]$, the latter of which includes the binary successor relation in addition to the linear ordering on string positions. For both languages, our structure theorems show exactly what is expressible using a given quantifier depth, $n$, and using $m$ blocks of alternating quantifiers, for any $mleq n$. Using these characterizations, we prove, among other results, that there is a strict hierarchy of alternating quantifiers for both languages. The question whether there was such a hierarchy had been completely open since it was asked in [Etessami, Vardi, and Wilke 1997].
Cite as

Philipp Weis and Neil Immerman. Structure Theorem and Strict Alternation Hierarchy for FO² on Words. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{weis_et_al:DagSemProc.06451.6,
  author =	{Weis, Philipp and Immerman, Neil},
  title =	{{Structure Theorem and Strict Alternation Hierarchy for FO\~{A}‚\^{A}² on Words}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6451},
  editor =	{Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.6},
  URN =		{urn:nbn:de:0030-drops-9751},
  doi =		{10.4230/DagSemProc.06451.6},
  annote =	{Keywords: Descriptive complexity, finite model theory, alternation hierarchy, Ehrenfeucht-Fraisse games}
}

Filters

  • Authors
  • D
  • Durand, Arnaud
  • H
  • Hesse, William
  • I
  • Immerman, Neil
  • L
  • Lautemann, Clemens
  • M
  • More, Malika
  • S
  • Schöning, Uwe
  • Schwentick, Thomas
  • T
  • Thérien, Denis
  • Torán, Jacobo
  • V
  • Vollmer, Heribert
  • W
  • Weis, Philipp

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact