close
1.

図書

図書
Afonso Ferreira, Horst Reichel (eds.)
出版情報: Berlin ; New York : Springer, c2001  xv, 576 p. ; 24 cm
シリーズ名: Lecture notes in computer science ; 2010
所蔵情報: loading…
目次情報: 続きを見る
Invited Presentations
Recurrence in Infinite Words (Extended Abstract) / Julien Cassaigne
Generalized Model-Checking Problems for First-Order Logic / Martin Grohe
Myhill-Nerode Relations on Automatic Systems and the Completeness of Kleene Algebra / Dexter Kozen
Contributions
2-Nested Simulation Is Not Finitely Equationally Axiomatizable / Luca Aceto ; Wan Fokkink ; Anna Ingólfsdóttir
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems / Shin Aida ; Rainer Schuler ; Tatsuie Tsukiji ; Osamu Watanabe
Matching Polygonal Curves with Respect to the Fréchet Distance / Helmut Alt ; Christian Knauer ; Carola Wenk
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata / Andris Ambainis ; Arnolds Kikusts ; M&amacron;ris Valdats
Star-Free Open Languages and Aperiodic Loops / Martin Beaudry ; Frangois Lemieux ; Denis Thérien
5\frac2n2-Lower Bound for the Multiplicative Complexity of n x n-Matrix Multiplication / Markus Bläser
Evasiveness of Subgraph Containment and Related Properties / Amit Chakrabarti ; Subhash Khot ; Yaoyun Shi
On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs / Andrea E.F. Clementi ; Pilu Crescenzi ; Paolo Penna ; Gianluca Rossi ; Paola Vocca
On Presburger Liveness of Discrete Timed Automata / Zhe Dang ; Pierluigi San Pietro ; Richard A. Kemmerer
Residual Finite State Automata / Fraçcois Denis ; Aurélien Lemay ; Alain Terlutte
Deterministic Radio Broadcasting at Low Cost / Anders Dessmark ; Andrzej Pelc
The Existential Theory of Equations with Rational Constraints in Free Groups is I'PSPACE Complete / Volker Diekert ; Claudio Gutiérrez ; Christian Hagenah
Recursive Randomized Coloring Beats Fair Dice Random Colorings / Benjamin Doerr ; Anand Srivastav
Randomness, Computability, and Density / Rod G. Downey ; Denis R. Hirschfeldt ; André Nies
On Multipartition Communication Complexity (Extended Abstract) / Pavol ĎDuriš ; Juraj Hromkovič ; Stasys Jukna ; Martin Sauerhoff ; Georg Schnitger
Scalable Sparse Topologies with Small Spectrum / Robert Elsäasser ; Rastilav Královič ; Burkhard Monien
Optimal Preemptive Scheduling on Uniform Processors with Non-decreasing Speed Ratios / Leah Epstein
The UPS Problem / Cristina G. Fernandes ; Till Nierhoff
Gathering of Asynchronous Oblivious Robots with Limited Visibility / Paola Flocchini ; Giuseppe Prencipe ; Nicola Santoro ; eter Widmayer
Generalized Langton's Ant: Dynamical Behavior and Complexity / Anahí Gajardo ; Eric Goles ; Andrés Moreira
Optimal and Approximate Station Placement in Networks (With Applications to Multicasting and Space Efficient Traversals) / Clemente Galdi ; Christos Kaklamanis ; Manuela Montangero ; Pino Persiano
Learning Expressions over Monoids (Extended Abstract) / Ricard Gavaldá
Efficient Recognition of Random Unsatisfiable fc-SAT Instances by Spectral Methods / Andreas Goerdt ; Michael Krivelevich
On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages / Massimiliano Goldwurm ; Beatrice Palano ; Massimo Santini
Efficient Minimal Perfect Hashing in Nearly Minimal Space / Torben Hagerup ; Torsten Tholey
Small PCPs with Low Query Complexity / Prahladh Harsha ; Madhu Sudan
Space Efficient Algorithms for Series-Parallel Graphs / Andreas Jakoby ; Maciej Liśkiewicz ; Rudiger Reischuk
A Toolkit for First Order Extensions of Monadic Games / David Janin ; Jerzy Marcinkowski
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs / Klaus Jansen ; Marek Karpinski ; Andrzej Lingas ; Eike Seidel
Refining the Hierarchy of Blind Multicounter Languages / Matthias Jantzen ; Alexy Kurganskyy
A Simple Undecidable Problem: The Inclusion Problem for Finite Substitutions on abc / Juhani Karhumdki ; Leonid P. Lisovik
New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata / Jarkko Kari ; Cristopher Moore
The Complexity of Minimal Satisfiability Problems / Lefteris M. Kirousis ; Phokion G. Kolaitis
On the Minimal Hardware Complexity of Pseudorandom Function Generators (Extended Abstract) / Matthias Krause ; Stefan Lucks
Approximation Algorithms for Minimum Size 2-Connectivity Problems / Piotr Krysta ; V.S. Anil Kumar
A Model Theoretic Proof of Buchi-Type Theorems and First-Order Logic for N-Free Pomsets / Dietrich Kuske
An Ehrenfeucht-Fraisse Approach to Collapse Results for First-Order Queries over Embedded Databases / Clemens Lautemann ; Nicole Schweikardt
A New Logical Characterization of Buuchi Automata / Giacomo Lenzi
A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraph / Liang Zhao ; Hiroshi Nagamochi ; Toshihide Ibaraki
The Complexity of Copy Constant Detection in Parallel Programs / Markus Müller-Olm
Approximation Algorithms for the Bottleneck Stretch Factor Problem / Giri Narasimhan ; Michiel Smid
Semantical Principles in the Modal Logic of Coalgebras / Dirk Pattinson
The #a = #b Pictures Are Recognizable / Klaus Reinhardt
A Logical Approach to Decidability of Hierarchies of Regular Star-Free Languages / Victor L. Selivanov
Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables / Howard Straubing
New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing / Philipp Woelfel
Author Index
Invited Presentations
Recurrence in Infinite Words (Extended Abstract) / Julien Cassaigne
Generalized Model-Checking Problems for First-Order Logic / Martin Grohe
2.

図書

図書
Horst Reichel (ed.)
出版情報: Berlin ; New York ; Tokyo : Springer-Verlag, c1995  ix, 433 p. ; 24 cm
シリーズ名: Lecture notes in computer science ; 965
所蔵情報: loading…
3.

図書

図書
Horst Reichel, Sophie Tison (eds.)
出版情報: Berlin : Springer, c2000  xiv, 662 p. ; 24 cm
シリーズ名: Lecture notes in computer science ; 1770
所蔵情報: loading…
目次情報: 続きを見る
Codes and Graphs / M. Amin Shokrollahi
A Classification of Symbolic Transition Systems / Thomas A. Henzinger ; Rupak Majumdar
Circuits versus Trees in Algebraic Complexity / Pascal Koiran
On the Many Faces of Block Codes / Kaustubh Deshmukh ; Priti Shankar ; Amitava Dasgupta ; B. Sundar Rajan
A New Algorithm for MAX-2-SAT / Edward A. Hirsch
Bias Invariance of Small Upper Spans / Jack H. Lutz ; Martin J. Strauss
The Complexity of Planarity Testing / Eric Allender ; Meena Mahajan
About Cube-Free Morphisms / Gwénaël Richomme ; Francis Wlazinski
Linear Cellular Automata with Multiple State Variables / Jarkko Kari
Two-Variable Word Equations / Lucian Hie ; Wojciech Plandowski
Average-Case Quantum Query Complexity / Andris Ambainis ; Ronald de Wolf
Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs / Juraj Hromkovič ; Martin Sauerhoff
The Boolean Hierarchy of NP-Partitions / Sven Kosub ; Klaus W. Wagner
Binary Exponential Backoff Is Stable for High Arrival Rates / Hesham Al-Ammal ; Leslie Ann Goldberg ; Phil MacKenzie
The Data Broadcast Problem with Preemption / Nicolas Schabanel
An Approximate Lp-Difference Algorithm for Massive Data Streams / Jessica H. Fong
Succinct Representations of Model Based Belief Revision / Paolo Penna
Logics Capturing Local Properties / Leonid Libkin
The Complexity of Poor Man's Logic / Edith Hemaspaandra
Fast Integer Sorting in Linear Space / Yijie Han
On the Performance of WEAK-HEAPSORT / Stefan Edelkamp ; Ingo Wegener
On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers / Luca Aceto ; Zoltán Ésik ; Anna Ingólfsdóttir
Real-Time Automata and the Kleene Algebra of Sets of Real Numbers. / Cătălin Dima
Small Progress Measures for Solving Parity Games / Marcin Jurdziński
Multi-linearity Self-Testing with Relative Error / Frédéric Magniez
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies / Vikraman Arvind ; Johannes Köbler ; Martin Mundhenk ; Jacobo Torán
Hard Instances of Hard Problems / Vikram Mhetre ; Sridhar Srinivasan
Simulation and Bisimulation over One-Counter Processes / Petr Jančar ; Antonín Kučera ; Faron Moller
Decidability of Reachability Problems for Classes of Two Counters Automata / Alain Finkel ; Grégoire Sutre
Hereditary History Preserving Bisimilarity Is Undecidable / Mogens Nielsen
The Hardness of Approximating Spanner Problems / Michael Elkin ; David Peleg
An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality / Hans-Joachim Böckenhauer ; Ralf Klasing ; Sebastian Seibert ; Walter Unger
λ-Coloring of Graphs / Hans L. Bodlaender ; Ton Kloks ; Richard B. Tan ; Jan van Leeuwen
Optimal Proof Systems and Sparse Sets / Harry Buhrman ; Steve Fenner ; Lance Fortnow ; Dieter van Melkebeek
Almost Complete Sets / Klaus Ambos-Spies ; Wolfgang Merkle ; Jan Reimann ; Sebastiaan A. Terwijn
Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results
An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications / Evripidis Bampis ; Rodolphe Giroudeau ; Jean-Claude König
Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem / Klaus Jansen ; Maxim I. Sviridenko
Controlled Conspiracy-2 Search / Ulf Lorenz
The Stability of Saturated Linear Dynamical Systems Is Undecidable / Vincent D. Blondel ; Olivier Bournez ; John N. Tsitsiklis
Tilings: Recursivity and Regularity / Julien Cervelle ; Bruno Durand
Listing All Potential Maximal Cliques of a Graph / Vincent Bouchitté ; loan Todinca
Distance Labeling Schemes for Well-Separated Graph Classes / Michal Katz ; Nir A. Katz
Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphs / Jean-Marc Lanlignel ; Olivier Raynaud ; Eric Thierry
Characterizing and Deciding MSO-Definability of Macro Tree Transductions / Joost Engelfriet ; Sebastian Maneth
Languages of Dot-Depth 3/2 / Christian Glaßer ; Heinz Schmitz
Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures / Alberto Bertoni ; Massimiliano Goldwurm ; Massimo Santini
The CNN Problem and Other fc-Server Variants / Elias Koutsoupias ; David Scot Taylor
The Weighted 2-Server Problem / Marek Chrobak ; Jiří Sgall
On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem / Yair Bartal
Spectral Bounds on General Hard Core Predicates / Mikael Goldmann ; Alexander Russell
Randomness in Visual Cryptography / Annalisa De Bonis ; Alfredo De Santis
Online Dial-a-Ride Problems: Minimizing the Completion Time / Norbert Ascheuer ; Sven O. Krumke ; Jörg Rambau
The Power Range Assignment Problem in Radio Networks on the Plane / Andrea E.F. Clementi ; Riccardo Silvestri
Author Index
Codes and Graphs / M. Amin Shokrollahi
A Classification of Symbolic Transition Systems / Thomas A. Henzinger ; Rupak Majumdar
Circuits versus Trees in Algebraic Complexity / Pascal Koiran
4.

電子ブック

EB
FCT '95, Horst Reichel
出版情報: SpringerLink Books Lecture Notes In Computer Science Archive , Springer Berlin Heidelberg, 1995
所蔵情報: loading…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼