Conference proceedings
© 1985

STACS 85

2nd Annual Symposium on Theoretical Aspects of Computer Science, Saarbrücken, January 3-5, 1985

Editors:

K. Mehlhorn

K. Mehlhorn

View editor publications

You can also search for this editor in PubMed Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 182)

5243 Accesses
169 Citations

Sections

Table of contents
Keywords
Bibliographic Information
Publish with us

Buy it now

Softcover Book USD 49.99

Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Learn about institutional subscriptions

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (36 papers)

Front Matter

PDF
On the relative complexity of subproblems of intractable problems
- Klaus Ambos-Spies
Pages 1-12
On Lovász' lattice reduction and the nearest lattice point problem
- László Babai
Pages 13-20
Layouts with wires of balanced length
- B. Becker, H. G. Osthof
Pages 21-31
On the single-operation worst-case time complexity of the disjoint set union problem
- Norbert Blum
Pages 32-38
Deterministic languages and non-generators
- L. Boasson, A. Petit
Pages 39-46
Simulation of large networks on smaller networks
- H. L. Bodlaender, J. van Leeuwen
Pages 47-58
Petri nets and algebraic calculi of processes
- Cérard Boudol, Cérard Roucairol, Robert de Simone
Pages 59-70
Non-deterministic two-tape automata are more powerful than deterministic ones
- W. Brauer, K. -J. Lange
Pages 71-79
Construction of a family of factorizing codes
- Clelia De Felice
Pages 80-86
On hotz groups and homomorphic images of sentential form languages
- Volker Diekert
Pages 87-97
Using domain algebras to prove the correctness of a compiler
- Peter Dybjer
Pages 98-108
Sorting and recognition problems for ordered sets
- Ulrich Faigle, György Turán
Pages 109-118
Tree automata and logic programs
- Gilberto Filé
Pages 119-130
Structure of relations satisfying certain families of dependencies
- Patrick C. Fischer, Dirk Van Gucht
Pages 131-142
A single source shortest path algorithm for a planar distributed network
- Greg N. Frederickson
Pages 143-150
An algorithm for two-layer channel routing
- Shaodi Gao
Pages 151-160
New algorithms for special cases of the hidden line elimination problem
- Ralf Hartmut Güting, Thomas Ottmann
Pages 161-172
An algorithm to construct Minkowski-reduced lattice-bases
- Bettina Helfrich
Pages 173-179
Base Non Finie de Varietes
- Christine Irastorza
Pages 180-186

Keywords

Factor
NP
Notation
algorithms
automata
compiler
complexity
derivation
grammars
logic
petri net
semantics
sorting
algorithm analysis and problem complexity

Bibliographic Information

Book Title: STACS 85
Book Subtitle: 2nd Annual Symposium on Theoretical Aspects of Computer Science, Saarbrücken, January 3-5, 1985
Editors: K. Mehlhorn
Series Title: Lecture Notes in Computer Science
DOI: https://doi.org/10.1007/BFb0023988
Publisher: Springer Berlin, Heidelberg
eBook Packages: Springer Book Archive
Copyright Information: Springer-Verlag Berlin Heidelberg 1985
Softcover ISBN: 978-3-540-13912-6Published: 01 December 1984
eBook ISBN: 978-3-540-39136-4Published: 19 November 2005
Series ISSN: 0302-9743
Series E-ISSN: 1611-3349
Edition Number: 1
Number of Pages: VII, 375
Topics: Algorithm Analysis and Problem Complexity, Mathematical Logic and Formal Languages, Computation by Abstract Devices, Models and Principles

Publish with us

Policies and ethics

Access via your institution

Buy it now

Softcover Book USD 49.99

Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Learn about institutional subscriptions