The abstracts
correspond to those versions of papers that were submitted originally.
Papers are ordered by the time of their submission.
Formal Series over Algebras
by Werner Kuich
[View abstract]Preemptive Scheduling with Dedicated Processors: Applications of Fractional Graph Coloring
by Klaus Jansen, Lorant Porkolab
[View abstract]Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
by Beate Bollig
[View abstract]On a Generalization of Bi-complement Reducible Graphs
by Vadim V. Lozin
[View abstract]Informative Labeling Schemes for Graphs
by David Peleg
[View abstract]Simplifying Flow Networks
by Therese Biedl, Brona Brejova, Tomas Vinar
[View abstract]Iteration Theories of Boolean Functions
by Z. Esik
[View abstract]Binary Decision Diagrams by Shared Rewriting
by Jaco van de Pol and Hans Zantema
[View abstract]Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems
by Steffen Reith and Heribert Vollmer
[View abstract]A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism
by Petr Savicky, Detlef Sieling
[View abstract]Embedding Fibonacci Cubes into Hypercubes with $\Omega(2^{cn})$ Faulty Nodes
by Rostislav Caha and Petr Gregor
[View abstract]Optical Routing of Uniform Instances in Tori
by Francesc Comellas, Margarida Mitjana, Lata Narayanan, and Jaroslav Opatrny
[View abstract]Periodic-like Words
by Arturo Carpi, Aldo de Luca
[View abstract]On the Lower Bounds for One-way Quantum Automata
by Farid Ablayev and Aida Gainutdinova
[View abstract]AI-matching is NP-complete
by Ondrej Klima, Jiri Srba
[View abstract]Separation Results for Rebound Automata
by Holger Petersen
[View abstract]Unary Pushdown Automata and Auxiliary Space Lower Bounds
by Giovanni Pighizzini
[View abstract]$\pi$-Calculus, Structured Coalgebras and Minimal HD-Automata
by Ugo Montanari and Marco Pistore
[View abstract]Equation Satisfiability and Program Satisfiability for Finite Monoids
by David Mix Barrington, Pierre McKenzie, Cris Moore, Pascal Tesson and Denis Therien
[View abstract]$\mu$-calculus Synthesis
by Orna Kupferman and Moshe Y. Vardi
[View abstract]Counter Machines: Decidable Properties and Applications to Verification Problems
by Oscar H. Ibarra, Jianwen Su, Zhe Dang, Tevfik Bultan, and Richard Kemmerer
[View abstract]An Automata-based Recognition Algorithm for Semi-extended Regular Expressions
by Hiroaki Yamamoto
[View abstract]State Space Reduction using Partial $\tau$-Confluence
by Jan Friso Groote and Jaco van de Pol
[View abstract]On Diving in Trees
by Thomas Schwentick
[View abstract]The Monadic Theory of Morphic Infinite Words and Generalizations
by Olivier Carton, Wolfgang Thomas
[View abstract]Factorizing Codes and Schutzenberger Conjectures
by Clelia De Felice
[View abstract]Timed Automata with Monotonic Activities
by Ruggero Lanotte, Andrea Maggiolo Schettini
[View abstract]Measure Theoretic Completeness Notions for the Exponential Time Classes
by Klaus Ambos-Spies
[View abstract]Abstract Syntax and Variable Binding for Linear Binders
by Miki Tanaka
[View abstract]Derivability in Locally Quantified Modal Logics via Translation in Set Theory
by Angelo Montanari, Alberto Policriti, Matteo Slanina
[View abstract]Explicit Fusions
by Philippa Gardner and Lucian Wischik
[View abstract]Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization
by Daniel Kral
[View abstract]On the Autoreducibility of Random Sequences
by Todd Ebert and Heribert Vollmer
[View abstract]On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems
by Sven Kosub
[View abstract]Subtractive Reductions and Complete Problems for Counting Complexity Classes
by Arnaud Durand, Miki Hermann, Phokion G. Kolaitis
[View abstract]Balanced $k$-Colorings
by T.C. Biedl, E. Cenek, T.M. Chan, E.D. Demaine, M.L. Demaine, R. Fleischer, Ming-Wei Wang
[View abstract]Verifying Single and Multi-mutator Garbage Collectors with Owicki-Gries in Isabelle/HOL
by Leonor Prensa Nieto and Javier Esparza
[View abstract]Hardness Results and Efficient Approximations for Radiocoloring in Planar Graphs
by D.A. Fotakis, S.E. Nikoletseas, V.G. Papadopoulou and P.G. Spirakis
[View abstract]The Infinite Versions of LogSpace!=P Are Consistent with the Axioms of Set Theory
by Gregory Lafitte and Jacques Mazoyer
[View abstract]Why so many Temporal Logics Climb Up the Trees?
by A. Rabinovich and S. Maoz
[View abstract]A Compositional Model for Confluent Dynamic Data-flow Networks
by Frank S. de Boer and Marcello M. Bonsangue
[View abstract]Reducing the Number of Solutions of NP Functions
by Lane Hemaspaandra, Mitsunori Ogihara, and Gerd Wechsung
[View abstract]Regularity of Congruential Graphs
by Tanguy Urvoy
[View abstract]An algorithm constructing the semilinear post* for 2-dim Reset/Transfer VASS
by A. Finkel, G. Sutre
[View abstract]Axiomatizing Fully Complete Models for ML Polymorphic Types
by Samson Abramsky and Marina Lenisa
[View abstract]Sublinear Ambiguity
by Klaus Wich
[View abstract]Alternating and Empty Alternating Auxiliary Stack Automata
by Markus Holzer and Pierre McKenzie
[View abstract]Automatic Graphs and Graph $D0L$-Systems
by Olivier Ly
[View abstract]A Family of NFA's which Need $2^n-\alpha$ Deterministic States
by Kazuo Iwama, Akihiro Matsuura and Mike Paterson
[View abstract]Compositional Characterizations of $\lambda$-terms Using Intersection Types
by M.Dezani-Ciancaglini, F.Honsell and Y.Motohama
[View abstract]Iterative Arrays with Small Time Bounds
by Thomas Buchholz, Andreas Klein, Martin Kutrib
[View abstract]Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks
by Stefan Dobrev
[View abstract]Expressiveness of Updatable Timed Automata
by Patricia Bouyer, Catherine Dufourd, Emmanuel Fleury, Antoine Petit
[View abstract]Edge-bisection of Chordal Rings
by Lali Barriere and J. Fabrega
[View abstract]XML Grammars
by Jean Berstel, Luc Boasson
[View abstract]Bilinear Functions and Trees over the $(\max,+)$ Semiring
by Sabrina Mantaci, Vincent D. Blondel, and Jean Mairesse
[View abstract]Regular Collections of Message Sequence Charts
by Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P.S. Thiagarajan
[View abstract]
