Mathematical Systems Theory, Volume 27

Volume 27, Number 1, January/February 1994

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

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

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

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

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

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