Combinatorics, Computation and Logic

by Calude, Cristian S.; Dinneen, M. J.

• ISBN13: 9789814021562
• ISBN10: 9814021563
• Format: Paperback
• Copyright: 1999-01-01
• Publisher: Eureka Pubns

Summary

Eine historistische Pfarrkirche, ein 'Museum der Zukunft' und eine Kulturinitiative liegen dicht gedrängt an einem kleinen Platz am Donauufer. Diese Institutionen verbindet nicht mehr, als daß sie im Laufe mehrerer Jahrhunderte im Linzer Stadtteil Alturfahr-Ost errichtet wurden. Was geschieht mit dem scheinbar unscheinbaren Ort, wenn Künstler ihn neu beleuchten und das vielschichtige Gefüge aus Bauten, Interessen und Ideologien sichtbar werden lassen? Was können künstlerische Interventionen im Stadtraum bewirken? Das Projekt Nexus wirft Fragen zu Kunst und Öffentlichkeit auf. Der Band stellt die kontroversen Ansätze von 12 KünstlerInnen vor und läßt sie ebenso wie Theoretiker und die beteiligten Stadtbewohner das Projekt reflektieren. Darüber hinaus umreißen Beiträge aus kunstwissenschaftlicher, philosophischer und medientheoretischer Perspektive auch den theoretischen Kontext von künstlerischen Interventionen im öffentlichen Raum. Am theoretischen Teil der Publikation haben neben den Herausgeberinnen mitgewirkt: M. Boeckl, A. R. Boelderl, H. Lachmayer, G. Stocker u. a. Das grafische Konzept stammt von Richard Ferkl. Zur Publikation erscheint ein Nexus-Video von O. Lasch.

Table of Contents

Invited papers
Parametric Complexity After (almost) Ten Years: Review and Open Questions	1	(33)
Rodney G. Downey
Michael R. Fellows
Hidden Algebra for Software Engineering	34	(26)
Joseph A. Goguen
On Negative Informations in Language Theory	60	(13)
Filippo Mignosi
Antonio Restivo
Crossroads in Flatland	73	(8)
Janos Pach
Efficiency vs. Security in the Implementation of Public-Key Cryptography	81	(25)
P. Gary Walsh
Contributed papers
No Feasible Monotone Interpolation for Cut-free Gentzen Type Propositional Calculus with Permutation Inference	106	(11)
Noriko H. Arai
Permuting Mechanisms and Closed Classes of Permutations	117	(11)
Michael D. Atkinson
Robert Beals
Process Algebra with Five-Valued Conditions	128	(16)
Jan A. Bergstra
Alban Ponse
A Stability Theorem for Recursive Analysis	144	(15)
Vasco Brattka
Languages Based on Structural Local Testability	159	(16)
Alessandra Cherubini
Stefano Crespi--Reghizzi
Pierluigi San Pietro
Towards Automatic Bisimilarity Checking in the Spi Calculus	175	(15)
Anders Strandløv Elkjær
Michael Hohle
Hans Huttel
Kasper Overgard
Three Remarks on SAGBI Bases for Polynomial Invariants of Permutation Groups	190	(12)
Manfred Gobel
Computing Prufer Codes Efficiently in Parallel	202	(15)
Raymond Greenlaw
Rossella Petreschi
Completeness Results for a Lazy Conditional Narrowing Calculus	217	(15)
Mohamed Hamada
Aart Middeldorp
Taro Suzuki
The Pagenumber of de Bruijn and Kautz Digraphs	232	(15)
Toru Hasunuma
Formal Synthesis for Pipeline Design	247	(15)
Holger Hinrichsen
Hans Eveking
Gerd Ritter
An O(n log n) Algorithm for Computing all Maximal Quasiperiodicities in Strings	262	(11)
Costas S. Iliopoulos
Laurent Mouchard
The Graphs of Finite Monadic Semi--Thue Systems Have a Decidable Monadic Second--Order Theory	273	(13)
Teodor Knapik
Huges Calbrix
Lown, Highn, and Intermediate Subrecursive Degrees	286	(15)
Lars Kristiansen
Star-extremal Circulant Graphs	301	(9)
Ko-Wei Lih
Daphne D.-F. Liu
Xuding Zhu
On the Approximability of Physical Map Problems using Single Molecule Methods	310	(19)
Laxmi Parida
On the Weakness of Conditional Equations in Algebraic Specification	329	(15)
Arno Schonegge
David Kempe
A Decision Algorithm for Prenex Normal Form Rational Presburger Sentences Based on Combinatorial Geometry	344	(16)
Naoki Shibata
Kozo Okano
Teruo Higashino
Kenichi Taniguchi
Lower Bounds on Negation-Limited Inverters	360
Shao Chin Sung
Keisuke Tanaka