Mathematical Systems Theory, Volume 27

Volume 27, Number 1, January/February 1994

Shimon Even, Ami Litman: On the Capabilities of Systolic Systems. 3-28 BibTeX
Geng Lin, Nicholas Pippenger: Parallel Algorithms for Routing in Nonblocking Networks. 29-40 BibTeX
Bojana Obrenic: An Approach To Emulating Separable Graphs. 41-63 BibTeX
Marios C. Papaefthymiou: Understanding Retiming Through Maximum Avarage-Delay Cycles. 65-84 BibTeX
Abhiram G. Ranade: Optimal Speedup for Backtrack Search on a Butterfly Network. 85-101 BibTeX

Gudmund Skovbjerg Frandsen, Mark Valence, David A. Mix Barrington: Some Results on Uniform Arithmetic Circuit Complexity. 105-124 BibTeX
Iain A. Stewart: On Completeness for NP via Projection Translations. 125-157 BibTeX
Andrzej Ehrenfeucht, Grzegorz Rozenberg, Kai Salomaa: Semantics of Trees. 159-181 BibTeX
Bin Fu, Hong-Zhou Li, Yong Zhong: An Application of the Translational Method. 183-186 BibTeX

Mitsunori Ogiwara: Generalized Theorems on Relationships Among Reducibility Notions to Certain Complexity Classes. 189-200 BibTeX
Ronald V. Book, Jack H. Lutz, Klaus W. Wagner: An Observation on Probability Versus Randomness with Applications to Complexity Classes. 201-209 BibTeX
Osamu Watanabe: A Framework for Polynomial-Time Query Learnability. 211-229 BibTeX
Osamu Watanabe, Ricard Gavaldà: Structural Analysis of Polynomial-Time Query Learnability. 231-256 BibTeX
Dieter Kratsch, Lane A. Hemaspaandra: On the Complexity of Graph Reconstruction. 257-273 BibTeX
Daniel Berend, Christiane Frougny: Computability by Finite Automata and Pisot Bases. 275-282 BibTeX

Helmut Seidl: Equivalence of Finite-Valued Tree Transducers Is Decidable. 285-346 BibTeX
Montserrat Hermo, Elvira Mayordomo: A Note on Polynomial-Size Circuits with Low Resource-Bounded Kolmogorov Complexity. 347-356 BibTeX
Alain Hertz: A New Polynomial-Time Algorithm for the Maximum Weighted (\chi(G) - 1)-Coloring Problem in Comparability Graphs. 357-363 BibTeX
Ming Li, Paul M. B. Vitányi: Statistical Properties of Finite Sequences with High Kolmogorov Complexity. 365-376 BibTeX

Robert F. Chamberlain, Charles M. Fiduccia: Universality of Iterated Networks. 381-430 BibTeX
Amotz Bar-Noy, Shlomo Kipnis: Designing Broadcasting Algorithms in the Postal Model for Message-Passing Systems. 431-452 BibTeX
Richard J. Anderson: Primitives for Asynchronous List Compression. 453-470 BibTeX
Christos Kaklamanis, Giuseppe Persiano: Branch-and-Bound and Backtrack Search on Mesh-Connected Arrays of Processors. 471-489 BibTeX
C. Greg Plaxton, Torsten Suel: A Lower Bound for Sorting Networks Based on the Shuffle Permutation. 491-508 BibTeX

K. Vijay-Shanker, David J. Weir: The Equivalence of Four Extensions of Context-Free Grammars. 511-546 BibTeX
Hagit Attiya, Marios Mavronicolas: Efficiency of Semisynchronous Versus. 547-571 BibTeX