Journal of Computer and System Sciences

2005

Partially ordered regular languages for graph queries
by: Sergio Flesca, Sergio Greco v. 70 i. 1 p. 1 - 25
Extracting fuzzy if-then rules by using the information matrix technique
by: Chongfu Huang, Claudio Moraga v. 70 i. 1 p. 26 - 52
Wire length as a circuit complexity measure
by: Robert A. Legenstein, Wolfgang Maass v. 70 i. 1 p. 53 - 72
Multiattribute decision making models and methods using intuitionistic fuzzy sets
by: Deng-Feng Li v. 70 i. 1 p. 73 - 85
Extracting the workflow critical path from the extended well-formed workflow schema
by: Jin Hyun Son, Jung Sun Kim, Myoung-Ho Kim v. 70 i. 1 p. 86 - 106
A provable better Branch and Bound method for a nonconvex integer quadratic programming problem
by: Wenxing Zhu v. 70 i. 1 p. 107 - 117
A parametric error analysis of Goldschmidt's division algorithm
by: Guy Even, Peter-Michael Seidel, Warren E. Ferguson v. 70 i. 1 p. 118 - 139
Efficiently parallelizable problems on a class of decomposable graphs
by: Sun-Yuan Hsieh v. 70 i. 1 p. 140 - 156
Language equations, maximality and error-detection
by: Lila Kari, Stavros Konstantinidis v. 70 i. 1 p. 157 - 178
First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
by: David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien v. 70 i. 2 p. 101 - 127
Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications
by: Michael Goldwasser, Ming-Yang Kao, Hsueh-I Lu v. 70 i. 2 p. 128 - 144
On paging with locality of reference
by: Susanne Albers, Lene M. Favrholdt, Oliver Giel v. 70 i. 2 p. 145 - 175
A probabilistic model of computing with words
by: Daowen Qiu, Huaiqing Wang v. 70 i. 2 p. 176 - 200
Delay-insensitive computation in asynchronous cellular automata
by: Jia Lee, Susumu Adachi, Ferdinand Peper, Shinro Mashiko v. 70 i. 2 p. 201 - 220
Attribute grammars for unranked trees as a query language for structured documents
by: Frank Neven v. 70 i. 2 p. 221 - 257
A local approach for temporal model checking of Java bytecode
by: Antonella Santone, Gigliola Vaglini v. 70 i. 2 p. 258 - 281
Guest Editors' foreword
by: Richard Karp, Ming Li, Pavel A. Pevzner, Ron Shamir v. 70 i. 3 p. 283
An O(n2) algorithm for signed translocation
by: Lusheng Wang, Daming Zhu, Xiaowen Liu, Shaohan Ma v. 70 i. 3 p. 284 - 299
A 1.5-approximation algorithm for sorting by transpositions and transreversals
by: Tzvika Hartman, Roded Sharan v. 70 i. 3 p. 300 - 320
Sorting signed permutations by reversals, revisited
by: Haim Kaplan, Elad Verbin v. 70 i. 3 p. 321 - 341
Designing seeds for similarity search in genomic DNA
by: Jeremy Buhler, Uri Keich, Yanni Sun v. 70 i. 3 p. 342 - 363
Vector seeds: An extension to spaced seeds
by: Brona Brejová, Daniel G. Brown, Tomás Vinar v. 70 i. 3 p. 364 - 380
Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained and structured recombination
by: Dan Gusfield v. 70 i. 3 p. 381 - 398
Designing optimally multiplexed SNP genotyping assays
by: Yonatan Aumann, Efrat Manisterski, Zohar Yakhini v. 70 i. 3 p. 399 - 417
An effective algorithm for peptide de novo sequencing from MS/MS spectra
by: Bin Ma, Kaizhong Zhang, Chengzhi Liang v. 70 i. 3 p. 418 - 430
Special issue on computational learning theory
by: Robert H. Sloan v. 70 i. 4 p. 433 - 434
Exact learning of DNF formulas using DNF hypotheses
by: Lisa Hellerstein, Vijay Raghavan v. 70 i. 4 p. 435 - 470
Exploring learnability between exact and PAC
by: Nader H. Bshouty, Jeffrey C. Jackson, Christino Tamon v. 70 i. 4 p. 471 - 484
New lower bounds for statistical query learning
by: Ke Yang v. 70 i. 4 p. 485 - 509
Increasing the power of uniform inductive learners
by: Sandra Zilles v. 70 i. 4 p. 510 - 538
Predictive complexity and information
by: Michael V. Vyugin, Vladimir V. V'yugin v. 70 i. 4 p. 539 - 554
Performance guarantees for hierarchical clustering
by: Sanjoy Dasgupta, Philip M. Long v. 70 i. 4 p. 555 - 569
Prediction and dimension
by: Lance Fortnow, Jack H. Lutz v. 70 i. 4 p. 570 - 589
Graph-based specification of access control policies
by: Manuel Koch, Luigi V. Mancini, Francesco Parisi-Presicce v. 71 i. 1 p. 1 - 33
Monotonic hybrid systems
by: Ruggero Lanotte, Andrea Maggiolo-Schettini v. 71 i. 1 p. 34 - 69
A self-stabilizing algorithm for the shortest path problem assuming read/write atomicity
by: Tetz C. Huang v. 71 i. 1 p. 70 - 85
Efficient parallel factorization and solution of structured and unstructured linear systems
by: John H. Reif v. 71 i. 1 p. 86 - 143
Tight approximability results for test set problems in bioinformatics
by: Piotr Berman, Bhaskar DasGupta, Ming-Yang Kao v. 71 i. 2 p. 145 - 162
An improved accuracy measure for rough sets
by: Baowen Xu, Yuming Zhou, Hongmin Lu v. 71 i. 2 p. 163 - 173
Kernels in planar digraphs
by: Gregory Gutin, Ton Kloks, Chuan-Min Lee, Anders Yeo v. 71 i. 2 p. 174 - 184
Threshold circuit lower bounds on cryptographic functions
by: Eike Kiltz, Hans-Ulrich Simon v. 71 i. 2 p. 185 - 212
General constructions for information-theoretic private information retrieval
by: Amos Beimel, Yuval Ishai, Eyal Kushilevitz v. 71 i. 2 p. 213 - 247

2004

Subword histories and Parikh matrices
by: Alexandru Mateescu, Arto Salomaa, Sheng Yu v. 68 i. 1 p. 1 - 21
Sensitivity analysis and efficient method for identifying optimal spaced seeds
by: Kwok Pui Choi, Louxin Zhang v. 68 i. 1 p. 22 - 40
Abstract Voronoi diagram in 3-space
by: Ngoc-Minh Lê v. 68 i. 1 p. 41 - 79
Average stretch without migration
by: Luca Becchetti, Stefano Leonardi, S. Muthukrishnan v. 68 i. 1 p. 80 - 95
Randomness and reducibility
by: Rodney G. Downey, Denis R. Hirschfeldt, Geoffrey LaForte v. 68 i. 1 p. 96 - 114
Some measures of dissimilarity in intuitionistic fuzzy structures
by: Deng-Feng Li v. 68 i. 1 p. 115 - 122
A necessary and sufficient condition for transforming limited accuracy failure detectors
by: Emmanuelle Anceaume, Antonio Fernández, Achour Mostéfaoui, Gil Neiger, Michel Raynal v. 68 i. 1 p. 123 - 133
Trees and learning
by: Wolfgang Merkle, Frank Stephan v. 68 i. 1 p. 134 - 156
Mixed Pfair/ERfair scheduling of asynchronous periodic tasks
by: James H. Anderson, Anand Srinivasan v. 68 i. 1 p. 157 - 204
More efficient PAC-learning of DNF with membership queries under the uniform distribution
by: Nader H. Bshouty, Jeffrey C. Jackson, Christino Tamon v. 68 i. 1 p. 205 - 234
Guest Editors' foreword
by: Sampath Kannan, Mihalis Yannakakis v. 68 i. 2 p. 237 - 237
A sharp threshold in proof complexity yields lower bounds for satisfiability search
by: Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy v. 68 i. 2 p. 238 - 268
Lower bounds for intersection searching and fractional cascading in higher dimension
by: Bernard Chazelle, Ding Liu v. 68 i. 2 p. 269 - 284
Computing crossing numbers in quadratic time
by: Martin Grohe v. 68 i. 2 p. 285 - 302
Learning DNF in time 2Õ(n1/3)
by: Adam R. Klivans, Rocco A. Servedio v. 68 i. 2 p. 303 - 318
Decidability of string graphs
by: Marcus Schaefer, Daniel Stefankovic v. 68 i. 2 p. 319 - 334
Optimal outlier removal in high-dimensional spaces
by: John Dunagan, Santosh Vempala v. 68 i. 2 p. 335 - 373
Quantitative solution of omega-regular games
by: Luca de Alfaro, Rupak Majumdar v. 68 i. 2 p. 374 - 397
A new protocol and lower bounds for quantum coin flipping
by: Andris Ambainis v. 68 i. 2 p. 398 - 416
Clustering to minimize the sum of cluster diameters
by: Moses Charikar, Rina Panigrahy v. 68 i. 2 p. 417 - 441
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
by: Michel X. Goemans, David P. Williamson v. 68 i. 2 p. 442 - 470
Computational complexity of compaction to irreflexive cycles
by: Narayan Vikas v. 68 i. 3 p. 473 - 496
Algebraic hierarchical graph transformation
by: Wojciech Palacz v. 68 i. 3 p. 497 - 520
Learning with side information: PAC learning bounds
by: Pirkko Kuusela, Daniel Ocone v. 68 i. 3 p. 521 - 545
Graph properties checkable in linear time in the number of vertices
by: Etienne Grandjean, Frédéric Olive v. 68 i. 3 p. 546 - 597
On the design of time-stamped signatures
by: Hung-Min Sun, Bing-Chang Chen, Her-Tyan Yeh v. 68 i. 3 p. 598 - 610
Branching synchronization grammars with nested tables
by: Frank Drewes, Joost Engelfriet v. 68 i. 3 p. 611 - 656
Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
by: Christopher M. Homan v. 68 i. 3 p. 657 - 674
On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
by: Pavol Duris, Juraj Hromkovic, Katsushi Inoue v. 68 i. 3 p. 675 - 699
Guest Editors' foreword
by: Edith Cohen, Venkatesan Guruswami v. 68 i. 4 p. 701 - 701
An information statistics approach to data stream and communication complexity
by: Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar v. 68 i. 4 p. 702 - 732
Decoding turbo-like codes via linear programming
by: Jon Feldman, David R. Karger v. 68 i. 4 p. 733 - 752
Testing juntas
by: Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky v. 68 i. 4 p. 753 - 787
Implicit B-trees: a new data structure for the dictionary problem
by: Gianni Franceschini, Roberto Grossi, J. Ian Munro, Linda Pagli v. 68 i. 4 p. 788 - 807
Learning intersections and thresholds of halfspaces
by: Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio v. 68 i. 4 p. 808 - 840
A spectral algorithm for learning mixture models
by: Santosh Vempala, Grant Wang v. 68 i. 4 p. 841 - 860
Guest editor's foreword
by: Anne Condon v. 69 i. 1 p. 1 - 2
Resolution lower bounds for perfect matching principles
by: Alexander A. Razborov v. 69 i. 1 p. 3 - 27
The correlation between parity and quadratic polynomials mod 3
by: Frederic Green v. 69 i. 1 p. 28 - 44
The inapproximability of lattice and coding problems with preprocessing
by: Uriel Feige, Daniele Micciancio v. 69 i. 1 p. 45 - 67
Hardness amplification within NP
by: Ryan O'Donnell v. 69 i. 1 p. 68 - 94
Scaled dimension and nonuniform complexity
by: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo v. 69 i. 2 p. 97 - 122
Robust learning--rich and poor
by: John Case, Sanjay Jain, Frank Stephan, Rolf Wiehagen v. 69 i. 2 p. 123 - 165
Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
by: Erik D. Demaine, Mohammad Taghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos v. 69 i. 2 p. 166 - 195
On approximating weighted sums with exponentially many terms
by: Deepak Chawla, Lin Li, Stephen Scott v. 69 i. 2 p. 196 - 234
Minimal DFA for testing divisibility
by: Boris Alexeev v. 69 i. 2 p. 235 - 243
A lower bound on the quantum query complexity of read-once functions
by: Howard Barnum, Michael E. Saks v. 69 i. 2 p. 244 - 258
On relations between counting communication complexity classes
by: Carsten Damm, Matthias Krause, Christoph Meinel, Stephan Waack v. 69 i. 2 p. 259 - 280
Network QoS games: stability vs optimality tradeoff
by: Andrew Lomonosov, Meera Sitharam, Kihong Park v. 69 i. 2 p. 281 - 302
Special issue: 35th Annual ACM Symposium on Theory of Computing
by: Sanjeev Khanna, Aravind Srinivasan v. 69 i. 3 p. 305
Random knapsack in expected polynomial time
by: René Beier, Berthold Vöcking v. 69 i. 3 p. 306 - 329
Integer priority queues with decrease key in constant time and the single source shortest paths problem
by: Mikkel Thorup v. 69 i. 3 p. 330 - 353
Testing subgraphs in directed graphs
by: Noga Alon, Asaf Shapira v. 69 i. 3 p. 354 - 382
Optimal oblivious routing in polynomial time
by: Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke v. 69 i. 3 p. 383 - 394
Exponential lower bound for 2-query locally decodable codes via a quantum argument
by: Iordanis Kerenidis, Ronald de Wolf v. 69 i. 3 p. 395 - 420
Learning functions of k relevant variables
by: Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio v. 69 i. 3 p. 421 - 434
Cell-probe lower bounds for the partial match problem
by: T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani v. 69 i. 3 p. 435 - 447
Classical complexity and quantum entanglement
by: Leonid Gurvits v. 69 i. 3 p. 448 - 484
A tight bound on approximating arbitrary metrics by tree metrics
by: Jittat Fakcharoenphol, Satish Rao, Kunal Talwar v. 69 i. 3 p. 485 - 497
On the reducibility of sets inside NP to sets with low information content
by: Mitsunori Ogihara, Till Tantau v. 69 i. 4 p. 499 - 524
Linear time algorithms for finding and representing all the tandem repeats in a string
by: Dan Gusfield, Jens Stoye v. 69 i. 4 p. 525 - 546
Approximating the dense set-cover problem
by: Reuven Bar-Yehuda, Zehavit Kehat v. 69 i. 4 p. 547 - 561
One-dimensional quantum walks with absorbing boundaries
by: Eric Bach, Susan Coppersmith, Marcel Paz Goldschen, Robert Joynt, John Watrous v. 69 i. 4 p. 562 - 592
On the computational power of circuits of spiking neurons
by: Wolfgang Maass, Henry Markram v. 69 i. 4 p. 593 - 616
An expressive language for linear spatial database queries
by: Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht v. 69 i. 4 p. 617 - 655
Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
by: Stefan Szeider v. 69 i. 4 p. 656 - 674
On complexity of single-minded auction
by: Ning Chen, Xiaotie Deng, Xiaoming Sun v. 69 i. 4 p. 675 - 687
Global robust stability of delayed neural networks with a class of general activation functions
by: He Huang, Jinde Cao, Yuzhong Qu v. 69 i. 4 p. 688 - 700

2003

Guest Editor's Foreword
by: Georg Gottlob v. 66 i. 1 p. 1 - 1
Analysis and application of adaptive sampling
by: James F. Lynch v. 66 i. 1 p. 2 - 19
Query containment for data integration systems
by: Todd D. Millstein, Alon Y. Halevy, Marc Friedman v. 66 i. 1 p. 20 - 39
Verification of relational transducers for electronic commerce
by: Marc Spielmann v. 66 i. 1 p. 40 - 65
Typechecking for XML transformers
by: Tova Milo, Dan Suciu, Victor Vianu v. 66 i. 1 p. 66 - 97
Generalized substring selectivity estimation
by: Zhiyuan Chen, Flip Korn, Nick Koudas, S. Muthukrishnan v. 66 i. 1 p. 98 - 132
On the content of materialized aggregate views
by: Stéphane Grumbach, Leonardo Tininini v. 66 i. 1 p. 133 - 168
Reachability and connectivity queries in constraint databases
by: Michael Benedikt, Martin Grohe, Leonid Libkin, Luc Segoufin v. 66 i. 1 p. 169 - 206
Indexing Moving Points
by: Pankaj K. Agarwal, Lars Arge, Jeff Erickson v. 66 i. 1 p. 207 - 243
Auditing Boolean attributes
by: Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan v. 66 i. 1 p. 244 - 253
Integrity constraints for XML
by: Wenfei Fan, Jérôme Siméon v. 66 i. 1 p. 254 - 291
TTL: a modular language for hardware/software systems design
by: Vincenza Carchiolo, Michele Malgeri, Giuseppe Mangioni v. 66 i. 2 p. 293 - 315
An axiomatic semantics for the synchronous language Gentzen
by: Simone Tini v. 66 i. 2 p. 316 - 348
An efficient fully polynomial approximation scheme for the Subset-Sum Problem
by: Hans Kellerer, Renata Mansini, Ulrich Pferschy, Maria Grazia Speranza v. 66 i. 2 p. 349 - 370
Approximate testing with error relative to input size
by: Marcos A. Kiwi, Frédéric Magniez, Miklos Santha v. 66 i. 2 p. 371 - 392
The complexity of the temporal logic with "until" over general linear time
by: Mark Reynolds v. 66 i. 2 p. 393 - 426
Quantum multi-prover interactive proof systems with limited prior entanglement
by: Hirotada Kobayashi, Keiji Matsumoto v. 66 i. 3 p. 429 - 450
Translation of binary regular expressions into nondeterministic [epsiv]-free automata with transitions
by: Viliam Geffert v. 66 i. 3 p. 451 - 472
Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines
by: Martin Sauerhoff v. 66 i. 3 p. 473 - 495
On the difficulty of approximately maximizing agreements
by: Shai Ben-David, Nadav Eiron, Philip M. Long v. 66 i. 3 p. 496 - 514
Blocking a transition in a free choice net and what it tells about its throughput
by: Bruno Gaujal, Stefan Haar, Jean Mairesse v. 66 i. 3 p. 515 - 548
Completeness results for graph isomorphism
by: Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán v. 66 i. 3 p. 549 - 566
Scheduling multicasts on unit-capacity trees and meshes
by: Monika Rauch Henzinger, Stefano Leonardi v. 66 i. 3 p. 567 - 611
Guest Editor's Foreword
by: Peter Buneman v. 66 i. 4 p. 613 - 613
Optimal aggregation algorithms for middleware
by: Ronald Fagin, Amnon Lotem, Moni Naor v. 66 i. 4 p. 614 - 656
Relaxed multi-way trees with group updates
by: Kim S. Larsen v. 66 i. 4 p. 657 - 670
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
by: Dimitris Achlioptas v. 66 i. 4 p. 671 - 687
XML with data values: typechecking revisited
by: Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu v. 66 i. 4 p. 688 - 727
Pipelining in multi-query optimization
by: Nilesh N. Dalvi, Sumit K. Sanghai, Prasan Roy, S. Sudarshan v. 66 i. 4 p. 728 - 762
Two-dimensional substring indexing
by: Paolo Ferragina, Nick Koudas, S. Muthukrishnan, Divesh Srivastava v. 66 i. 4 p. 763 - 774
Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width
by: Georg Gottlob, Nicola Leone, Francesco Scarcello v. 66 i. 4 p. 775 - 808
Querying websites using compact skeletons
by: Anand Rajaraman, Jeffrey D. Ullman v. 66 i. 4 p. 809 - 851
A simple reduction of non-uniformity in dynamic load balancing of quantized loads on hypercube multiprocessors and hiding balancing overheads
by: Hwakyung Rim, Ju-wook Jang, Sung-Chun Kim v. 67 i. 1 p. 1 - 25
Stability of long-lived consensus
by: Shlomi Dolev, Sergio Rajsbaum v. 67 i. 1 p. 26 - 45
On parallel attribute-efficient learning
by: Peter Damaschke v. 67 i. 1 p. 46 - 62
Constant time parallel sorting: an empirical view
by: William I. Gasarch, Evan Golub, Clyde P. Kruskal v. 67 i. 1 p. 63 - 91
Connection caching: model and algorithms
by: Edith Cohen, Haim Kaplan, Uri Zwick v. 67 i. 1 p. 92 - 126
Proof theory of higher-order equations: conservativity, normal forms and term rewriting
by: Karl Meinke v. 67 i. 1 p. 127 - 173
Remarks on permutive cellular automata
by: Jean-Paul Allouche, Guentcho Skordev v. 67 i. 1 p. 174 - 182
Preemptive scheduling in overloaded systems
by: Marek Chrobak, Leah Epstein, John Noga, Jiri Sgall, Rob van Stee, Tomás Tichý, Nodari Vakhania v. 67 i. 1 p. 183 - 197
Scheduling loosely connected task graphs
by: Abhiram G. Ranade v. 67 i. 1 p. 198 - 208
Guest Editor's Foreword
by: John H. Reif v. 67 i. 2 p. 211 - 211
Random sampling and approximation of MAX-CSPs
by: Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski v. 67 i. 2 p. 212 - 243
Computing the Betti numbers of arrangements via spectral sequences
by: Saugata Basu v. 67 i. 2 p. 244 - 262
Clifford algebras and approximating the permanent
by: Steve Chien, Lars Eilstrup Rasmussen, Alistair Sinclair v. 67 i. 2 p. 263 - 290
A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
by: Mary Cryan, Martin E. Dyer v. 67 i. 2 p. 291 - 310
On the complexity of price equilibria
by: Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra v. 67 i. 2 p. 311 - 324
Fitting algebraic curves to noisy data
by: Sanjeev Arora, Subhash Khot v. 67 i. 2 p. 325 - 340
The price of anarchy is independent of the network topology
by: Tim Roughgarden v. 67 i. 2 p. 341 - 364
Recognizing string graphs in NP
by: Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic v. 67 i. 2 p. 365 - 380
Optimal finger search trees in the pointer machine
by: Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Athanasios K. Tsakalidis, Kostas Tsichlas v. 67 i. 2 p. 381 - 418
Pseudo-random generators for all hardnesses
by: Christopher Umans v. 67 i. 2 p. 419 - 440
Almost all graphs with average degree 4 are 3-colorable
by: Dimitris Achlioptas, Cristopher Moore v. 67 i. 2 p. 441 - 471
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
by: Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis v. 67 i. 3 p. 473 - 496
Automatic graphs and D0L-sequences of finite graphs
by: Olivier Ly v. 67 i. 3 p. 497 - 545
Intrinsic complexity of learning geometrical concepts from positive data
by: Sanjay Jain, Efim B. Kinber v. 67 i. 3 p. 546 - 607
One-way permutations and self-witnessing languages
by: Christopher M. Homan, Mayur Thakur v. 67 i. 3 p. 608 - 622
Complex-valued wavelet network
by: Chunguang Li, Xiaofeng Liao, Juebang Yu v. 67 i. 3 p. 623 - 632
On the approximability of clique and related maximization problems
by: Aravind Srinivasan v. 67 i. 3 p. 633 - 651
Foreword from the guest editors
by: Jianer Chen, Michael R. Fellows v. 67 i. 4 p. 653 - 653
The Turing way to parameterized complexity
by: Marco Cesati v. 67 i. 4 p. 654 - 685
The k-FEATURE SET problem is W[2]-complete
by: Carlos Cotta, Pablo Moscato v. 67 i. 4 p. 686 - 690
Solving large FPT problems on coarse-grained parallel machines
by: James Cheetham, Frank K. H. A. Dehne, Andrew Rau-Chaplin, Ulrike Stege, Peter J. Taillon v. 67 i. 4 p. 691 - 706
Call control with k rejections
by: R. Sai Anand, Thomas Erlebach, Alexander Hall, Stamatis Stefanakos v. 67 i. 4 p. 707 - 722
A fixed-parameter algorithm for minimum quartet inconsistency
by: Jens Gramm, Rolf Niedermeier v. 67 i. 4 p. 723 - 741
The parametrized complexity of knot polynomials
by: Johann A. Makowsky, Julian Mariño v. 67 i. 4 p. 742 - 756
On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
by: Krzysztof Pietrzak v. 67 i. 4 p. 757 - 771
Improving a fixed parameter tractability time bound for the shadow problem
by: Peter Heusch, Stefan Porschen, Ewald Speckenmeyer v. 67 i. 4 p. 772 - 788
On the existence of subexponential parameterized algorithms
by: Liming Cai, David W. Juedes v. 67 i. 4 p. 789 - 807
Graph separators: a parameterized view
by: Jochen Alber, Henning Fernau, Rolf Niedermeier v. 67 i. 4 p. 808 - 832
Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
by: Jianer Chen, Iyad A. Kanj v. 67 i. 4 p. 833 - 847

2002

Special Issue on COLT 2000 - Guest Editor's Foreword
by: Sally A. Goldman v. 64 i. 1 p. 1 - 1
A New Abstract Combinatorial Dimension for Exact Learning via Queries
by: José L. Balcázar, Jorge Castro, David Guijarro v. 64 i. 1 p. 2 - 21
The Computational Complexity of Densest Region Detection
by: Shai Ben-David, Nadav Eiron, Hans-Ulrich Simon v. 64 i. 1 p. 22 - 47
Adaptive and Self-Confident On-Line Learning Algorithms
by: Peter Auer, Nicolò Cesa-Bianchi, Claudio Gentile v. 64 i. 1 p. 48 - 75
Relative Expected Instantaneous Loss Bounds
by: Jürgen Forster, Manfred K. Warmuth v. 64 i. 1 p. 76 - 102
Boosting Using Branching Programs
by: Yishay Mansour, David A. McAllester v. 64 i. 1 p. 103 - 112
Drifting Games and Brownian Motion
by: Yoav Freund, Manfred Opper v. 64 i. 1 p. 113 - 132
Estimation and Approximation Bounds for Gradient-Based Reinforcement Learning
by: Peter L. Bartlett, Jonathan Baxter v. 64 i. 1 p. 133 - 150
Inductive Inference with Additional Information
by: Mark A. Fulk v. 64 i. 2 p. 153 - 159
Efficient Approximation Algorithms for the SUBSET-SUMS EQUALITY Problem
by: Cristina Bazgan, Miklos Santha, Zsolt Tuza v. 64 i. 2 p. 160 - 170
Formal Software Specification with Refinements and Modules of Typed Graph Transformation Systems
by: Martin Große-Rhode, Francesco Parisi-Presicce, Marta Simeoni v. 64 i. 2 p. 171 - 218
Competitive On-line Scheduling of Continuous-Media Streams
by: Minos N. Garofalakis, Yannis E. Ioannidis, Banu Özden, Abraham Silberschatz v. 64 i. 2 p. 219 - 248
Hierarchical Graph Transformation
by: Frank Drewes, Berthold Hoffmann, Detlef Plump v. 64 i. 2 p. 249 - 283
Minimality of an Automaton Cascade Decomposition for Learning System Environments
by: Tom H. Westerdale v. 64 i. 2 p. 284 - 307
Context-Free Languages of Sub-exponential Growth
by: Martin R. Bridson, Robert H. Gilman v. 64 i. 2 p. 308 - 310
Reducing the Number of Solutions of NP Functions
by: Lane A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung v. 64 i. 2 p. 311 - 328
Interval Consistency of Asynchronous Distributed Computations
by: Jean-Michel Hélary, Achour Mostéfaoui, Michel Raynal v. 64 i. 2 p. 329 - 349
Output String Languages of Compositions of Deterministic Macro Tree Transducers
by: Joost Engelfriet, Sebastian Maneth v. 64 i. 2 p. 350 - 395
LTL Is Expressively Complete for Mazurkiewicz Traces
by: Volker Diekert, Paul Gastin v. 64 i. 2 p. 396 - 418
Lower Bounds for Linearly Transformed OBDDs and FBDDs
by: Detlef Sieling v. 64 i. 2 p. 419 - 438
Special Issue on PODS 1999 - Guest Editors' Foreword
by: Yannis E. Ioannidis, Christos H. Papadimitriou v. 64 i. 3 p. 441 - 442
Rewriting of Regular Expressions and Regular Path Queries
by: Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi v. 64 i. 3 p. 443 - 465
Inherent Complexity of Recursive Queries
by: Stavros S. Cosmadakis v. 64 i. 3 p. 466 - 495
Maximizing Sharing of Protected Information
by: Steven Dawson, Sabrina De Capitani di Vimercati, Patrick Lincoln, Pierangela Samarati v. 64 i. 3 p. 496 - 541
A Framework for Measuring Differences in Data Characteristics
by: Venkatesh Ganti, Johannes Gehrke, Raghu Ramakrishnan, Wei-Yin Loh v. 64 i. 3 p. 542 - 578
Hypertree Decompositions and Tractable Queries
by: Georg Gottlob, Nicola Leone, Francesco Scarcello v. 64 i. 3 p. 579 - 627
Aggregate Operators in Constraint Query Languages
by: Michael Benedikt, Leonid Libkin v. 64 i. 3 p. 628 - 654
Querying Incomplete Information in Semistructured Data
by: Yaron Kanza, Werner Nutt, Yehoshua Sagiv v. 64 i. 3 p. 655 - 693
Polymorphic Type Inference for the Relational Algebra
by: Jan Van den Bussche, Emmanuel Waller v. 64 i. 3 p. 694 - 718
Tracking Join and Self-Join Sizes in Limited Storage
by: Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy v. 64 i. 3 p. 719 - 747
Guest Editor's Foreword
by: Sanjeev Khanna v. 64 i. 4 p. 749 - 749
Quantum Lower Bounds by Quantum Arguments
by: Andris Ambainis v. 64 i. 4 p. 750 - 767
Finding Smooth Integers in Short Intervals Using CRT Decoding
by: Dan Boneh v. 64 i. 4 p. 768 - 784
Query Strategies for Priced Information
by: Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai v. 64 i. 4 p. 785 - 819
Connectivity and Inference Problems for Temporal Networks
by: David Kempe, Jon M. Kleinberg, Amit Kumar v. 64 i. 4 p. 820 - 842
A New Proof of the Weak Pigeonhole Principle
by: Alexis Maciel, Toniann Pitassi, Alan R. Woods v. 64 i. 4 p. 843 - 872
Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model
by: Omer Barkol, Yuval Rabani v. 64 i. 4 p. 873 - 896
Guest Editor's Foreword
by: Lenore Cowen, Ronald Fagin, Joe Kilian, Jon M. Kleinberg v. 65 i. 1 p. 1 - 1
Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions
by: Miklós Ajtai v. 65 i. 1 p. 2 - 37
Optimal Bounds for the Predecessor Problem and Related Problems
by: Paul Beame, Faith E. Fich v. 65 i. 1 p. 38 - 72
Finding Similar Regions in Many Sequences
by: Ming Li, Bin Ma, Lusheng Wang v. 65 i. 1 p. 73 - 96
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors
by: Ran Raz, Omer Reingold, Salil P. Vadhan v. 65 i. 1 p. 97 - 128
A Constant-Factor Approximation Algorithm for the k-Median Problem
by: Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys v. 65 i. 1 p. 129 - 149
A Fully Dynamic Algorithm for Maintaining the Transitive Closure
by: Valerie King, Garry Sagert v. 65 i. 1 p. 150 - 167
Reducibility between Classes of Port Graph Grammar
by: Charles A. Stewart v. 65 i. 2 p. 169 - 223
Online Learning of Binary and n-ary Relations over Clustered Domains
by: Atsuyoshi Nakamura, Naoki Abe v. 65 i. 2 p. 224 - 256
New Lowness Results for ZPPNP and Other Complexity Classes
by: Vikraman Arvind, Johannes Köbler v. 65 i. 2 p. 257 - 277
Some Decision Problems Concerning Semilinearity and Commutation
by: Tero Harju, Oscar H. Ibarra, Juhani Karhumäki, Arto Salomaa v. 65 i. 2 p. 278 - 294
An Algorithm for Handling Many Relational Calculus Queries Efficiently
by: Dan E. Willard v. 65 i. 2 p. 295 - 331
On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts
by: Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter v. 65 i. 2 p. 332 - 350
Node Replacements in Embedding Normal Form
by: Konstantin Skodinis, Egon Wanke v. 65 i. 2 p. 351 - 376
The Equivalence Problem for DF0L Languages and Power Series
by: Juha Honkala v. 65 i. 2 p. 377 - 392
Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds
by: Giovanni Pighizzini, Jeffrey Shallit, Ming-wei Wang v. 65 i. 2 p. 393 - 414
Generalization Error of Combined Classifiers
by: Llew Mason, Peter L. Bartlett, Mostefa Golea v. 65 i. 2 p. 415 - 438
Foreword
by: Ming Li, Pavel A. Pevzner, Ron Shamir v. 65 i. 3 p. 441 - 441
Reconstructing an ancestral genome using minimum segments duplications and reversals
by: Nadia El-Mabrouk v. 65 i. 3 p. 442 - 464
The longest common subsequence problem for sequences with nested arc annotations
by: Guo-Hui Lin, Zhi-Zhong Chen, Tao Jiang, Jianjun Wen v. 65 i. 3 p. 465 - 480
Combining polynomial running time and fast convergence for the disk-covering method
by: Jens Lagergren v. 65 i. 3 p. 481 - 493
Methods for reconstructing the history of tandem repeats and their application to the human genome
by: Deep Jaitly, Paul E. Kearney, Guo-Hui Lin, Bin Ma v. 65 i. 3 p. 494 - 507
Steps toward accurate reconstructions of phylogenies from gene-order data
by: Bernard M. E. Moret, Jijun Tang, Li-San Wang, Tandy Warnow v. 65 i. 3 p. 508 - 525
The restriction mapping problem revisited
by: Gopal Pandurangan, Ramesh Hariharan v. 65 i. 3 p. 526 - 544
The consensus string problem and the complexity of comparing hidden Markov models
by: Rune B. Lyngsø, Christian N. S. Pedersen v. 65 i. 3 p. 545 - 569
Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis
by: Yaw-Ling Lin, Tao Jiang, Kun-Mao Chao v. 65 i. 3 p. 570 - 586
Efficient algorithms for multichromosomal genome rearrangements
by: Glenn Tesler v. 65 i. 3 p. 587 - 609
Foreword
by: Madhu Sudan v. 65 i. 4 p. 611 - 611
A linear lower bound on the unbounded error probabilistic communication complexity
by: Jürgen Forster v. 65 i. 4 p. 612 - 625
Monotone simulations of non-monotone proofs
by: Albert Atserias, Nicola Galesi, Pavel Pudlák v. 65 i. 4 p. 626 - 638
Affine projections of symmetric polynomials
by: Amir Shpilka v. 65 i. 4 p. 639 - 659
On the complexity of approximating the VC dimension
by: Elchanan Mossel, Christopher Umans v. 65 i. 4 p. 660 - 671
In search of an easy witness: exponential time vs. probabilistic polynomial time
by: Russell Impagliazzo, Valentine Kabanets, Avi Wigderson v. 65 i. 4 p. 672 - 694
Uniform constant-depth threshold circuits for division and iterated multiplication
by: William Hesse, Eric Allender, David A. Mix Barrington v. 65 i. 4 p. 695 - 716
Universal traversal sequences with backtracking
by: Michal Koucký v. 65 i. 4 p. 717 - 726

2001

Full Intersection Types and Topologies in Lambda Calculus
by: Silvia Ghilezan v. 62 i. 1 p. 1 - 14
Semantics and Expressive Power of Nondeterministic Constructs in Deductive Databases
by: Fosca Giannotti, Dino Pedreschi, Carlo Zaniolo v. 62 i. 1 p. 15 - 42
Belief Revision and Update: Complexity of Model Checking
by: Paolo Liberatore, Marco Schaerf v. 62 i. 1 p. 43 - 72
A Process-Calculus Analysis of Concurrent Operations on B-Trees
by: Anna Philippou, David Walker v. 62 i. 1 p. 73 - 122
Agnostic Learning of Geometric Patterns
by: Sally A. Goldman, Stephen Kwek, Stephen D. Scott v. 62 i. 1 p. 123 - 151
On the Benefit of Supporting Virtual Channels in Wormhole Routers
by: Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman v. 62 i. 1 p. 152 - 177
Robust Learning Is Rich
by: Sanjay Jain, Carl H. Smith, Rolf Wiehagen v. 62 i. 1 p. 178 - 212
Guest Editor's Foreword
by: Lance Fortnow v. 62 i. 2 p. 215 - 215
Computational Arithmetic Geometry I. Sentences Nearly in the Polynomial Hierarchy
by: J. Maurice Rojas v. 62 i. 2 p. 216 - 235
Pseudorandom Generators without the XOR Lemma
by: Madhu Sudan, Luca Trevisan, Salil P. Vadhan v. 62 i. 2 p. 236 - 266
Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes
by: Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi v. 62 i. 2 p. 267 - 289
Graph Ramsey Theory and the Polynomial Hierarchy
by: Marcus Schaefer v. 62 i. 2 p. 290 - 322
The Communication Complexity of Pointer Chasing
by: Stephen Ponzio, Jaikumar Radhakrishnan, S. Venkatesh v. 62 i. 2 p. 323 - 355
A Lower Bound for Primality
by: Eric Allender, Michael E. Saks, Igor Shparlinski v. 62 i. 2 p. 356 - 366
On the Complexity of k-SAT
by: Russell Impagliazzo, Ramamohan Paturi v. 62 i. 2 p. 367 - 375
Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity
by: John Watrous v. 62 i. 2 p. 376 - 391
Competitive Routing of Virtual Circuits with Unknown Duration
by: Baruch Awerbuch, Yossi Azar, Serge A. Plotkin, Orli Waarts v. 62 i. 3 p. 385 - 397
Parallel Output-Sensitive Algorithms for Combinatorial and Linear Algebra Problems
by: John H. Reif v. 62 i. 3 p. 398 - 412
Synthesizing Learners Tolerating Computable Noisy Data
by: John Case, Sanjay Jain v. 62 i. 3 p. 413 - 441
The Stability of Saturated Linear Dynamical Systems Is Undecidable
by: Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis v. 62 i. 3 p. 442 - 462
On ACTL Formulas Having Linear Counterexamples
by: Francesco Buccafurri, Thomas Eiter, Georg Gottlob, Nicola Leone v. 62 i. 3 p. 463 - 515
Improved Bounds on the Sample Complexity of Learning
by: Yi Li, Philip M. Long, Aravind Srinivasan v. 62 i. 3 p. 516 - 527
Estimation on Domain of Attraction and Convergence Rate of Hopfield Continuous Feedback Neural Networks
by: Jinde Cao, Qing Tao v. 62 i. 3 p. 528 - 534
Refinements of Complexity Results on Type Consistency for Object-Oriented Databases
by: Yasunori Ishihara, Shougo Shimizu, Hiroyuki Seki, Minoru Ito v. 62 i. 4 p. 537 - 564
Translating Regular Expressions into Small -Free Nondeterministic Finite Automata
by: Juraj Hromkovic, Sebastian Seibert, Thomas Wilke v. 62 i. 4 p. 565 - 588
Linear-Consistency Testing
by: Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan v. 62 i. 4 p. 589 - 607
Separation Results for Separated Apex NLC and NCE Graph Languages
by: Changwook Kim v. 62 i. 4 p. 608 - 628
The Descriptive Complexity Approach to LOGCFL
by: Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer v. 62 i. 4 p. 629 - 652
New Error Bounds for Solomonoff Prediction
by: Marcus Hutter v. 62 i. 4 p. 653 - 667
Verification by Augmented Abstraction: The Automata-Theoretic View
by: Yonit Kesten, Amir Pnueli, Moshe Y. Vardi v. 62 i. 4 p. 668 - 690
Editor's Foreword
by: Fan Chung Graham v. 63 i. 1 p. 1 - 1
Fairness in Routing and Load Balancing
by: Jon M. Kleinberg, Yuval Rabani, Éva Tardos v. 63 i. 1 p. 2 - 20
Sharing the Cost of Multicast Transmissions
by: Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker v. 63 i. 1 p. 21 - 41
Recommendation Systems: A Probabilistic Analysis
by: Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins v. 63 i. 1 p. 42 - 61
Combining Fairness with Throughput: Online Routing with Multiple Objectives
by: Ashish Goel, Adam Meyerson, Serge A. Plotkin v. 63 i. 1 p. 62 - 79
The Combinatorics of Cache Misses during Matrix Multiplication
by: Philip J. Hanlon, Dean Chung, Siddhartha Chatterjee, Daniela Genius, Alvin R. Lebeck, Erin Parker v. 63 i. 1 p. 80 - 126
Compression Using Efficient Multicasting
by: Micah Adler, Frank Thomson Leighton v. 63 i. 1 p. 127 - 145
Gust Editor's Foreword
by: Pavel Pudlák v. 63 i. 2 p. 147 - 147
The Communication Complexity of Enumeration, Elimination, and Selection
by: Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet v. 63 i. 2 p. 148 - 185
On the Complexity of Some Problems on Groups Input as Multiplication Tables
by: David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie v. 63 i. 2 p. 186 - 200
Quantum Kolmogorov Complexity
by: André Berthiaume, Wim van Dam, Sophie Laplante v. 63 i. 2 p. 201 - 221
Branching Program Size Is Almost Linear in Formula Size
by: Oliver Giel v. 63 i. 2 p. 222 - 235
Easiness Assumptions and Hardness Tests: Trading Time for Zero Error
by: Valentine Kabanets v. 63 i. 2 p. 236 - 252
A Lower Bound for the Shortest Path Problem
by: Ketan Mulmuley, Pradyut Shah v. 63 i. 2 p. 253 - 267
Time-Space Tradeoffs for SAT on Nonuniform Machines
by: Iannis Tourlakis v. 63 i. 2 p. 268 - 287
Integer Circuit Evaluation Is PSPACE-Complete
by: Ke Yang v. 63 i. 2 p. 288 - 303
Language Learning from Texts: Degrees of Intrinsic Complexity and Their Characterizations
by: Sanjay Jain, Efim B. Kinber, Rolf Wiehagen v. 63 i. 3 p. 305 - 354
Quantum Neural Networks
by: Sanjay Gupta, R. K. P. Zia v. 63 i. 3 p. 355 - 383
Tight Lower Bounds on the Size of Sweeping Automata
by: Hing Leung v. 63 i. 3 p. 384 - 393
Logic over Words on Denumerable Ordinals
by: Nicolas Bedon v. 63 i. 3 p. 394 - 431
Distance Realization Problems with Applications to Internet Tomography
by: Fan R. K. Chung, Mark W. Garrett, Ronald L. Graham, David Shallcross v. 63 i. 3 p. 432 - 448
Spectral Methods for Matrix Rigidity with Applications to Size-Depth Trade-offs and Communication Complexity
by: Satyanarayana V. Lokam v. 63 i. 3 p. 449 - 473
Low Complexity Variants of the Arrow Distributed Directory
by: David Peleg, Eilon Reshef v. 63 i. 3 p. 474 - 485
A Polynomial-time Algorithm for the Bistable Roommates Problem
by: Jay Sethuraman, Chung-Piaw Teo v. 63 i. 3 p. 486 - 497
A Slight Sharpening of LMN
by: Johan Håstad v. 63 i. 3 p. 498 - 508
Guest Editor's Foreword
by: Rajeev Motwani v. 63 i. 4 p. 511 - 511
Which Problems Have Strongly Exponential Complexity?
by: Russell Impagliazzo, Ramamohan Paturi, Francis Zane v. 63 i. 4 p. 512 - 530
A Randomized Approximation Scheme for Metric MAX-CUT
by: Wenceslas Fernandez de la Vega, Claire Kenyon v. 63 i. 4 p. 531 - 541
Time-Space Tradeoffs for Branching Programs
by: Paul Beame, T. S. Jayram, Michael E. Saks v. 63 i. 4 p. 542 - 572
Protocols for Asymmetric Communication Channels
by: Micah Adler, Bruce M. Maggs v. 63 i. 4 p. 573 - 596
The Minimum Equivalent DNF Problem and Shortest Implicants
by: Christopher Umans v. 63 i. 4 p. 597 - 611
Perfect Information Leader Election in log* n+O (1) Rounds
by: Alexander Russell, David Zuckerman v. 63 i. 4 p. 612 - 626
On Approximate Nearest Neighbors under linfinity Norm
by: Piotr Indyk v. 63 i. 4 p. 627 - 638
Heuristics for Semirandom Graph Problems
by: Uriel Feige, Joe Kilian v. 63 i. 4 p. 639 - 671
Randomness vs Time: Derandomization under a Uniform Assumption
by: Russell Impagliazzo, Avi Wigderson v. 63 i. 4 p. 672 - 688

2000

On the Inapproximability of Disjoint Paths and Minimum Steiner Forest with Bandwidth Constraints
by: Bin Ma, Lusheng Wang v. 60 i. 1 p. 1 - 12
Rooted Branching Bisimulation as a Congruence
by: Wan Fokkink v. 60 i. 1 p. 13 - 37
Global Exponential Stability and Periodic Solutions of Delayed Cellular Neural Networks
by: Jinde Cao v. 60 i. 1 p. 38 - 46
On Relationships between Statistical Zero-Knowledge Proofs
by: Tatsuaki Okamoto v. 60 i. 1 p. 47 - 108
Data Independence of Read, Write, and Control Structures in PRAM Computations
by: Klaus-Jörn Lange, Rolf Niedermeier v. 60 i. 1 p. 109 - 144
A 5/4 Linear Time Bin Packing Algorithm
by: József Békési, Gábor Galambos, Hans Kellerer v. 60 i. 1 p. 145 - 160
Computational Sample Complexity and Attribute-Efficient Learning
by: Rocco A. Servedio v. 60 i. 1 p. 161 - 178
Estimation of the Domain of Attraction and the Convergence Rate of a Hopfield Associative Memory and an Application
by: Jinde Cao, Qing Tao v. 60 i. 1 p. 179 - 186
Deciding Bisimilarity and Similarity for Probabilistic Processes
by: Christel Baier, Bettina Engelen, Mila E. Majster-Cederbaum v. 60 i. 1 p. 187 - 231
Editor's Foreword
by: Vijay Raghavan v. 60 i. 2 p. 233 - 233
Robust Learning Aided by Context
by: John Case, Sanjay Jain, Matthias Ott, Arun Sharma, Frank Stephan v. 60 i. 2 p. 234 - 257
Structural Results about Exact Learning with Unspecified Attribute Values
by: Andreas Birkendorf, Norbert Klasner, Christian Kuhlmann, Hans-Ulrich Simon v. 60 i. 2 p. 258 - 277
Sample Complexity of Model-Based Search
by: Christopher D. Rosin v. 60 i. 2 p. 278 - 301
An Average-Case Optimal One-Variable Pattern Language Learner
by: Rüdiger Reischuk, Thomas Zeugmann v. 60 i. 2 p. 302 - 335
Editor's Foreword
by: José L. Balcázar v. 60 i. 2 p. 336 - 336
Time-Space Tradeoffs for Satisfiability
by: Lance Fortnow v. 60 i. 2 p. 337 - 353
Reversible Space Equals Deterministic Space
by: Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp v. 60 i. 2 p. 354 - 367
Circuits and Expressions with Nonassociative Gates
by: Cristopher Moore, Denis Thérien, François Lemieux, Joshua Berman, Arthur Drisko v. 60 i. 2 p. 368 - 394
On TC0, AC0, and Arithmetic Circuits
by: Manindra Agrawal, Eric Allender, Samir Datta v. 60 i. 2 p. 395 - 421
Circuits over PP and PL
by: Richard Beigel, Bin Fu v. 60 i. 2 p. 422 - 441
Inequalities for Shannon Entropy and Kolmogorov Complexity
by: Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin v. 60 i. 2 p. 442 - 464
Undecidability Results for Low Complexity Time Classes
by: Rodney G. Downey, André Nies v. 60 i. 2 p. 465 - 479
Guest Editor's Foreword
by: Fan Chung Graham v. 60 i. 3 p. 481 - 481
Adaptive Packet Routing for Bursty Adversarial Traffic
by: William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén v. 60 i. 3 p. 482 - 509
Approximating the Bandwidth via Volume Respecting Embeddings
by: Uriel Feige v. 60 i. 3 p. 510 - 539
On the Limits of Nonapproximability of Lattice Problems
by: Oded Goldreich, Shafi Goldwasser v. 60 i. 3 p. 540 - 563
An Improved Approximation Algorithm for MULTIWAY CUT
by: Gruia Calinescu, Howard J. Karloff, Yuval Rabani v. 60 i. 3 p. 564 - 574
On Indexed Data Broadcast
by: Sanjeev Khanna, Shiyu Zhou v. 60 i. 3 p. 575 - 591
Protecting Data Privacy in Private Information Retrieval Schemes
by: Yael Gertner, Yuval Ishai, Eyal Kushilevitz, Tal Malkin v. 60 i. 3 p. 592 - 629
Min-Wise Independent Permutations
by: Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher v. 60 i. 3 p. 630 - 659
The Closure of Monadic NP
by: Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer v. 60 i. 3 p. 660 - 716
Spot-Checkers
by: Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan v. 60 i. 3 p. 717 - 751
A Comparison of Tree Transductions Defined by Monadic Second Order Logic and by Attribute Grammars
by: Roderick Bloem, Joost Engelfriet v. 61 i. 1 p. 1 - 50
New Efficient and Secure Protocols for Verifiable Signature Sharing and Other Applications
by: Dario Catalano, Rosario Gennaro v. 61 i. 1 p. 51 - 80
Improved Algorithms via Approximations of Probability Distributions
by: Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan v. 61 i. 1 p. 81 - 107
Computing with Membranes
by: Gheorghe Paun v. 61 i. 1 p. 108 - 143
Guest Editor's Forword
by: Jan Paredaens v. 61 i. 2 p. 145 - 145
Path Constraints in Semistructured Databases
by: Peter Buneman, Wenfei Fan, Scott Weinstein v. 61 i. 2 p. 146 - 193
Efficient Searching with Linear Constraints
by: Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter v. 61 i. 2 p. 194 - 216
Latent Semantic Indexing: A Probabilistic Analysis
by: Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala v. 61 i. 2 p. 217 - 235
Relational Transducers for Electronic Commerce
by: Serge Abiteboul, Victor Vianu, Brad S. Fordham, Yelena Yesha v. 61 i. 2 p. 236 - 269
Querying Spatial Databases via Topological Invariants
by: Luc Segoufin, Victor Vianu v. 61 i. 2 p. 270 - 301
Conjunctive-Query Containment and Constraint Satisfaction
by: Phokion G. Kolaitis, Moshe Y. Vardi v. 61 i. 2 p. 302 - 332
Separating NP-Completeness Notions under Strong Hypotheses
by: Klaus Ambos-Spies, Levke Bentzien v. 61 i. 3 p. 335 - 361
The Security of the Cipher Block Chaining Message Authentication Code
by: Mihir Bellare, Joe Kilian, Phillip Rogaway v. 61 i. 3 p. 362 - 399
On the No-Z-Cycle Property in Distributed Executions
by: Francesco Quaglia, Roberto Baldoni, Bruno Ciciani v. 61 i. 3 p. 400 - 427
Testing Problems with Sublearning Sample Complexity
by: Michael J. Kearns, Dana Ron v. 61 i. 3 p. 428 - 456
A Fault-Tolerance Model for Multiprocessor Real-Time Systems
by: Sheng-Tzong Cheng, Chia-Mei Chen, Satish K. Tripathi v. 61 i. 3 p. 457 - 477
On the Difference of Horn Theories
by: Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino v. 61 i. 3 p. 478 - 507
AVL Trees with Relaxed Balance
by: Kim S. Larsen v. 61 i. 3 p. 508 - 522
The Lob-Pass Problem
by: Jun-ichi Takeuchi, Naoki Abe, Shun-ichi Amari v. 61 i. 3 p. 523 - 557
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems
by: Beate Bollig, Ingo Wegener v. 61 i. 3 p. 558 - 579

1999

Mining Optimized Association Rules for Numeric Attributes
by: Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, Takeshi Tokuyama v. 58 i. 1 p. 1 - 12
Managing Conflicts Between Rules
by: H. V. Jagadish, Alberto O. Mendelzon, Inderpal Singh Mumick v. 58 i. 1 p. 13 - 28
Topological Queries in Spatial Databases
by: Christos H. Papadimitriou, Dan Suciu, Victor Vianu v. 58 i. 1 p. 29 - 53
Temporal Connectives Versus Explicit Timestamps to Query Temporal Databases
by: Serge Abiteboul, Laurent Herr, Jan Van den Bussche v. 58 i. 1 p. 54 - 68
Answering Queries Using Limited External Query Processors
by: Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman v. 58 i. 1 p. 69 - 82
Combining Fuzzy Information from Multiple Systems
by: Ronald Fagin v. 58 i. 1 p. 83 - 99
A Constant-Factor Approximation Algorithm for the k-MST Problem
by: Avrim Blum, R. Ravi, Santosh Vempala v. 58 i. 1 p. 101 - 108
On the Boosting Ability of Top-Down Decision Tree Learning Algorithms
by: Michael J. Kearns, Yishay Mansour v. 58 i. 1 p. 109 - 128
Characterizing Linear Size Circuits in Terms of Pricacy
by: Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén v. 58 i. 1 p. 129 - 136
The Space Complexity of Approximating the Frequency Moments
by: Noga Alon, Yossi Matias, Mario Szegedy v. 58 i. 1 p. 137 - 147
Extracting Randomness: A Survey and New Constructions
by: Noam Nisan, Amnon Ta-Shma v. 58 i. 1 p. 148 - 173
A Note on the Influence of an epsilon-Biased Random Source
by: Amir Ben-Dor, Anna R. Karlin, Nathan Linial, Yuri Rabinovich v. 58 i. 1 p. 174 - 176
Deciding the Vapnik-Cervonenkis Dimension in Sigmap3-Complete
by: Marcus Schaefer v. 58 i. 1 p. 177 - 182
On the Learnability of Rich Function Classes
by: Joel Ratsaby, Vitaly Maiorov v. 58 i. 1 p. 183 - 192
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems
by: Sanjeev Arora, David R. Karger, Marek Karpinski v. 58 i. 1 p. 193 - 210
Maximal Machine Learnable Classes
by: John Case, Mark A. Fulk v. 58 i. 1 p. 211 - 214
A Self-Stabilizing Distributed Algorithm to Find the Median of a Tree Graph
by: Gheorghe Antonoiu, Pradip K. Srimani v. 58 i. 1 p. 215 - 221
Paging Against a Distribution and IP Networking
by: Carsten Lund, Steven Phillips, Nick Reingold v. 58 i. 1 p. 222 - 232
Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers
by: Leslie Ann Goldberg, Philip D. MacKenzie v. 58 i. 1 p. 232 - 258
Algorithms for Matrix Groups and the Tits Alternative
by: Robert Beals v. 58 i. 2 p. 260 - 279
Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis
by: Jin-yi Cai, D. Sivakumar v. 58 i. 2 p. 280 - 296
Transforming Curves on Surfaces
by: Tamal K. Dey, Sumanta Guha v. 58 i. 2 p. 297 - 325
An Exponential Lower Bound for the Size of Monotone Real Circuits
by: Armin Haken, Stephen A. Cook v. 58 i. 2 p. 326 - 335
Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions
by: Moni Naor, Omer Reingold v. 58 i. 2 p. 336 - 375
BP HSpace(S) subseteq DSPACE(S3/2)
by: Michael E. Saks, Shiyu Zhou v. 58 i. 2 p. 376 - 403
On the Complexity of Database Queries
by: Christos H. Papadimitriou, Mihalis Yannakakis v. 58 i. 3 p. 407 - 427
Regular Path Queries with Constraints
by: Serge Abiteboul, Victor Vianu v. 58 i. 3 p. 428 - 452
Cut and Paste
by: Giansalvatore Mecca, Paolo Atzeni v. 58 i. 3 p. 453 - 482
Complete Geometric Query Languages
by: Marc Gyssens, Jan Van den Bussche, Dirk Van Gucht v. 58 i. 3 p. 483 - 511
Equivalence of Keyed Relational Schemas by Conjunctive Queries
by: Joseph Albert, Yannis E. Ioannidis, Raghu Ramakrishnan v. 58 i. 3 p. 512 - 534
On the Decidability of Semilinearity for Semialgebraic Sets and Its Implications for Spatial Databases
by: Freddy Dumortier, Marc Gyssens, Luc Vandeurzen, Dirk Van Gucht v. 58 i. 3 p. 535 - 571
The Computational Complexity of Some Problems of Linear Algebra
by: Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey Shallit v. 58 i. 3 p. 572 - 596
Attractors of Linear Cellular Automata
by: Giovanni Manzini, Luciano Margara v. 58 i. 3 p. 597 - 610
Stack Cooperation in Multistack Pushdown Automata
by: Jürgen Dassow, Victor Mitrana v. 58 i. 3 p. 611 - 621
Tight Bound on Johnson's Algorithm for Maximum Satisfiability
by: Jianer Chen, Donald K. Friesen, Hao Zheng v. 58 i. 3 p. 622 - 640
The Complexity of Finding a Second Hmiltonian Cycle in Cubic Graphs
by: Adam Krawczyk v. 58 i. 3 p. 641 - 647
Creating Strong, Total, Commutative, Associative One-Way Functions from Any One-Way Function in Complexity Theory
by: Lane A. Hemaspaandra, Jörg Rothe v. 58 i. 3 p. 648 - 659
A Technique for Proving Decidability of Containment and Equivalence of Linear Constraint Queries
by: Oscar H. Ibarra, Jiawen Su v. 59 i. 1 p. 1 - 28
Replication and Consistency in a Distributed Environment
by: Yuri Breitbart, Henry F. Korth v. 59 i. 1 p. 29 - 69
The Learnability of Unions of Two Rectangles in the Two-Dimensional Discretized Space
by: Zhixiang Chen, Foued Ameur v. 59 i. 1 p. 70 - 83
A Self-Stabilizing Algorithm for Detecting Fundamental Cycles in a Graph
by: Pranay Chaudhuri v. 59 i. 1 p. 84 - 93
Constraint-Generating Dependencies
by: Marianne Baudinet, Jan Chomicki, Pierre Wolper v. 59 i. 1 p. 94 - 115
Reasoning about Strings in Databases
by: Gösta Grahne, Matti Nykänen, Esko Ukkonen v. 59 i. 1 p. 116 - 162
Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds
by: Eric Allender, Klaus Reinhardt, Shiyu Zhou v. 59 i. 2 p. 164 - 181
Two Queries
by: Harry Buhrman, Lance Fortnow v. 59 i. 2 p. 182 - 194
On Arithmetic Branching Programs
by: Amos Beimel, Anna Gál v. 59 i. 2 p. 195 - 220
Approximating the SVP to within a Factor (1+1/dimxi) Is NP-Hard under Randomized Reductions
by: Jin-yi Cai, Ajay Nerurkar v. 59 i. 2 p. 221 - 239
Complexity Limitations on Quantum Computation
by: Lance Fortnow, John D. Rogers v. 59 i. 2 p. 240 - 252
Computational Indistinguishability: A Sample Hierarchy
by: Oded Goldreich, Madhu Sudan v. 59 i. 2 p. 253 - 269
On Membership Comparable Sets
by: D. Sivakumar v. 59 i. 2 p. 270 - 280
Space-Bounded Quantum Complexity
by: John Watrous v. 59 i. 2 p. 281 - 326
Hard Sets Are Hard to Find
by: Harry Buhrman, Dieter van Melkebeek v. 59 i. 2 p. 327 - 345
Arthur-Merlin Games in Boolean Decision Trees
by: Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin v. 59 i. 2 p. 346 - 372
Petri Net Languages and Infinite Subsets of m
by: Stephane Gaubert, Alessandro Giua v. 59 i. 3 p. 373 - 391
Analysis of Two Gradient-Based Algorithms for On-Line Regression
by: Nicolò Cesa-Bianchi v. 59 i. 3 p. 392 - 411
Models of Nondeterministic Regular Expressions
by: Flavio Corradini, Rocco De Nicola, Anna Labella v. 59 i. 3 p. 412 - 449
Graph Isomorphism and Identification Matrices: Sequential Algorithms
by: Lin Chen v. 59 i. 3 p. 450 - 475
Petri Nets and Regular Processes
by: Petr Jancar, Javier Esparza, Faron Moller v. 59 i. 3 p. 476 - 503
Bistable Versions of the Marriages and Roommates Problems
by: Bob P. Weems v. 59 i. 3 p. 504 - 520
Structure of the Invertible CA Transformations Group
by: Leo Liberti v. 59 i. 3 p. 521 - 536
Selective Mu-Calculus and Formula-Based Equivalence of Transition Systems
by: Roberto Barbuti, Nicoletta De Francesco, Antonella Santone, Gigliola Vaglini v. 59 i. 3 p. 537 - 556
On the Decidability of Semilinearity for Semialgebraic Sets and Its Implications for Spatial Databases - CORRIGENDUM
by: Freddy Dumortier, Marc Gyssens, Luc Vandeurzen, Dirk Van Gucht v. 59 i. 3 p. 557 - 562

1998

Regular Sequence Operations and Their Use in Database Queries
by: Seymour Ginsburg, Xiaoyang Sean Wang v. 56 i. 1 p. 1 - 26
Trading Independent for Synchronized Parallelism in Finite Copying Parallel Rewriting Systems
by: Giorgio Satta v. 56 i. 1 p. 27 - 45
Transforming a Single-Valued Transducer Into a Mealy Machine
by: Andreas Weber v. 56 i. 1 p. 46 - 59
Invertible Linear Cellular Automata over Zm: Algorithmic and Dynamical Aspects
by: Giovanni Manzini, Luciano Margara v. 56 i. 1 p. 60 - 67
On Correctness of Nonserializable Executions
by: Rajeev Rastogi, Sharad Mehrotra, Yuri Breitbart, Henry F. Korth, Abraham Silberschatz v. 56 i. 1 p. 68 - 82
TAL Recognition in O(M(n»)) Time
by: Sanguthevar Rajasekaran, Shibu Yooseph v. 56 i. 1 p. 83 - 89
Lower Bounds on the Multiparty Communication Complexity
by: Pavol Duris, José D. P. Rolim v. 56 i. 1 p. 90 - 95
Counting Protocols for Reliable End-to-End Transmission
by: Richard E. Ladner, Anthony LaMarca, Ewan D. Tempero v. 56 i. 1 p. 96 - 111
On Interpolating Arithmetic Read-Once Formulas with Exponentiation
by: Daoud Bshouty, Nader H. Bshouty v. 56 i. 1 p. 112 - 124
Remarks about Commutative Context-Free Languages
by: Juha Kortelainen v. 56 i. 1 p. 125 - 129
On the Learnability and Usage of Acyclic Probabilistic Finite Automata
by: Dana Ron, Yoram Singer, Naftali Tishby v. 56 i. 2 p. 133 - 152
A Game of Prediction with Expert Advice
by: V. G. Vovk v. 56 i. 2 p. 153 - 173
Prediction, Learning, Uniform Convergence, and Scale-Sensitive Dimensions
by: Peter L. Bartlett, Philip M. Long v. 56 i. 2 p. 174 - 190
Specification and Simulation of Statistical Query Algorithms for Efficiency and Noise Tolerance
by: Javed A. Aslam, Scott E. Decatur v. 56 i. 2 p. 191 - 208
Learning with Unreliable Boundary Queries
by: Avrim Blum, Prasad Chalasani, Sally A. Goldman, Donna K. Slonim v. 56 i. 2 p. 209 - 222
Covering Cubes by Random Half Cubes with Applications to Binary Neural Networks
by: Jeong Han Kim, James R. Roche v. 56 i. 2 p. 223 - 252
2-Testability and Relabelings Produce Everything
by: Lucian Ilie, Arto Salomaa v. 56 i. 3 p. 253 - 262
A Lower Bound for Perceptrons and an Oracle Separation of the PPPH Hierarchy
by: Christer Berg, Staffan Ulfberg v. 56 i. 3 p. 263 - 271
A Note on Batch and Incremental Learnability
by: Arun Sharma v. 56 i. 3 p. 272 - 276
Learning with Restricted Focus of Attention
by: Shai Ben-David, Eli Dichterman v. 56 i. 3 p. 277 - 298
A Fast Algorithm for Query Optimization in Universal-Relation Databases
by: Francesco M. Malvestuto, Marina Moscarini v. 56 i. 3 p. 299 - 309
Attribute-Efficient Learning in Query and Mistake-Bound Models
by: Nader H. Bshouty, Lisa Hellerstein v. 56 i. 3 p. 310 - 319
Optimal Circular Arc Representations: Properties, Recognition, and Construction
by: Lin Chen v. 56 i. 3 p. 320 - 331
The Equivalence of Bottom-Up and Top-Down Tree-to-Graph Transducers
by: Joost Engelfriet, Heiko Vogler v. 56 i. 3 p. 332 - 356
The Relative Complexity of NP Search Problems
by: Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi v. 57 i. 1 p. 3 - 19
What Do We Know about the Metropolis Algorithm?
by: Persi Diaconis, Laurent Saloff-Coste v. 57 i. 1 p. 20 - 36
On Data Structures and Asymmetric Communication Complexity
by: Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson v. 57 i. 1 p. 37 - 49
Randomized Query Processing in Robot Path Planning
by: Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, Prabhakar Raghavan v. 57 i. 1 p. 50 - 66
Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks
by: Jon M. Kleinberg, Éva Tardos v. 57 i. 1 p. 61 - 73
Sorting in Linear Time?
by: Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman v. 57 i. 1 p. 74 - 93
What's Decidable about Hybrid Automata?
by: Thomas A. Henzinger, Peter W. Kopke, Anuj Puri, Pravin Varaiya v. 57 i. 1 p. 94 - 124
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem
by: Manindra Agrawal, Eric Allender, Steven Rudich v. 57 i. 2 p. 127 - 143
Integer Programming as a Framework for Optimization and Approximability
by: Ian Barland, Phokion G. Kolaitis, Madhukar N. Thakur v. 57 i. 2 p. 144 - 161
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle
by: Samuel R. Buss, Toniann Pitassi v. 57 i. 2 p. 162 - 171
DNA Models and Algorithms for NP-Complete Problems
by: Eric Bach, Anne Condon, Elton Glaser, Celena Tanguay v. 57 i. 2 p. 172 - 186
Zero Knowledge and the Chromatic Number
by: Uriel Feige, Joe Kilian v. 57 i. 2 p. 187 - 199
Nondeterministic NC1 Computation
by: Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer v. 57 i. 2 p. 200 - 212
Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets
by: Dieter van Melkebeek v. 57 i. 2 p. 213 - 232
Sequences, Datalog, and Transducers
by: Anthony J. Bonner, Giansalvatore Mecca v. 57 i. 3 p. 234 - 259
Safe Locking Policies for Dynamic Databases
by: Vinay K. Chaudhri, Vassos Hadzilacos v. 57 i. 3 p. 260 - 271
Algebras for Querying Text Regions: Expressive Power and Optimization
by: Mariano P. Consens, Tova Milo v. 57 i. 3 p. 272 - 288
Arity Bounds in First-Order Incremental Evaluation and Definition of Polynomial Time Database Queries
by: Guozhu Dong, Jianwen Su v. 57 i. 3 p. 289 - 308
Increasing the Resilience of Distributed and Replicated Database Systems
by: Idit Keidar, Danny Dolev v. 57 i. 3 p. 309 - 324
Semantics and Expressiveness Issues in Active Databases
by: Philippe Picouet, Victor Vianu v. 57 i. 3 p. 325 - 355
Learning with Refutation
by: Sanjay Jain v. 57 i. 3 p. 356 - 365
Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth
by: Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, Prabhakar Ragde v. 57 i. 3 p. 366 - 375
Approximating Hyper-Rectangles: Learning and Pseudorandom Sets
by: Peter Auer, Philip M. Long, Aravind Srinivasan v. 57 i. 3 p. 376 - 388
Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy
by: Eugene Asarin, Oded Maler v. 57 i. 3 p. 389 - 398
A Three-Party Communication Problem
by: Leonard J. Schulman v. 57 i. 3 p. 399 - 401

1997

Comparison of Functional and Predicative Query Paradigms
by: Catriel Beeri, Tova Milo v. 54 i. 1 p. 3 - 33
A Semideterministic Approach to Object Creation and Nondeterminism in Database Queries
by: Jan Van den Bussche, Dirk Van Gucht v. 54 i. 1 p. 34 - 47
Tie-Breaking Semantics and Structural Totality
by: Christos H. Papadimitriou, Mihalis Yannakakis v. 54 i. 1 p. 48 - 60
On the Equivalence of Recursive and Nonrecursive Datalog Programs
by: Surajit Chaudhuri, Moshe Y. Vardi v. 54 i. 1 p. 61 - 78
Monotonic Aggregation in Deductive Database
by: Kenneth A. Ross, Yehoshua Sagiv v. 54 i. 1 p. 79 - 97
Knowledgebase Transformations
by: Gösta Grahne, Alberto O. Mendelzon, Peter Z. Revesz v. 54 i. 1 p. 98 - 112
The Complexity of Querying Indefinite Data about Linearly Ordered Domains
by: Ron van der Meyden v. 54 i. 1 p. 113 - 135
Reusing and Modifying Rulebases by Predicate Substitution
by: Anthony J. Bonner, Tomasz Imielinski v. 54 i. 1 p. 136 - 166
Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks
by: Marek Karpinski, Angus Macintyre v. 54 i. 1 p. 169 - 176
A Weak Version of the Blum, Shub, and Smale Model
by: Pascal Koiran v. 54 i. 1 p. 177 - 189
Neural Networks with Quadratic VC Dimension
by: Pascal Koiran, Eduardo D. Sontag v. 54 i. 1 p. 190 - 198
On the Computation of Boolean Functions by Analog Circuits of Bounded Fan-In
by: György Turán, Farrokh Vatan v. 54 i. 1 p. 199 - 212
Fully Parallelized Multi-Prover Protocols for NEXP-Time
by: Dror Lapidot, Adi Shamir v. 54 i. 2 p. 215 - 220
Better Lower Bounds for Monotone Threshold Formulas
by: Jaikumar Radhakrishnan v. 54 i. 2 p. 221 - 226
Connected Components in O (log^3/2 n) Parallel Time for the CREW PRAM
by: Donald B. Johnson, Panagiotis Takis Metaxas v. 54 i. 2 p. 227 - 242
All Pairs Shortest Paths for Graphs with Small Integer Length Edges
by: Zvi Galil, Oded Margalit v. 54 i. 2 p. 243 - 254
On the Exponent of the All Pairs Shortest Path Problem
by: Noga Alon, Zvi Galil, Oded Margalit v. 54 i. 2 p. 255 - 262
Breaking the Theta (n log² n) Barrier for Sorting with Faults
by: Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton v. 54 i. 2 p. 265 - 304
A Spectrum of Time-Space Trade-Offs for Undirected s-t Connectivity
by: Uriel Feige v. 54 i. 2 p. 305 - 316
The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations
by: Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk v. 54 i. 2 p. 317 - 331
Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers
by: Charles E. Leiserson, Satish Rao, Sivan Toledo v. 54 i. 2 p. 332 - 344
When Can We Sort in o(n log n) Time?
by: Amir M. Ben-Amram v. 54 i. 2 p. 345 - 370
Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution
by: Avrim Blum, Ravindran Kannan v. 54 i. 2 p. 371 - 380
DSPACE(n) = NSPACE(n): A Degree Theoretic Characterization
by: Manindra Agrawal v. 54 i. 3 p. 383 - 392
An Excursion to the Kolmogorov Random Strings
by: Harry Buhrman, Elvira Mayordomo v. 54 i. 3 p. 393 - 399
Counting Quantifiers, Successor Relations, and Logarithmic Space
by: Kousha Etessami v. 54 i. 3 p. 400 - 411
The Isomorphism Conjecture Holds and One-Way Functions Exists Relative to an Oracle
by: John D. Rogers v. 54 i. 3 p. 412 - 423
Semantics vs Syntax vs Computations: Machine Models for Type-2 Polynomial-Time Bounded Functionals
by: James S. Royer v. 54 i. 3 p. 424 - 436
On P-Immunity of Exponential Time Complete Sets
by: Nicholas Q. Trân v. 54 i. 3 p. 437 - 440
The Expressive Powers of Stable Models for Bound and Unbound DATALOG Queries
by: Domenico Saccà v. 54 i. 3 p. 441 - 464
On Fixed-Parameter Tractability and Approximability of NP Optimization Problems
by: Liming Cai, Jianer Chen v. 54 i. 3 p. 465 - 474
Geometric Approach for Optimal Routing on a Mesh with Buses
by: Yosi Ben-Asher, Ilan Newman v. 54 i. 3 p. 475 - 486
A Model of Interactive Teaching
by: H. David Mathias v. 54 i. 3 p. 487 - 501
A Completeness Theorem for the Expressive Power of Higher-Order Algebraic Specifications
by: Karl Meinke v. 54 i. 3 p. 502 - 519
Faster Shortest-Path Algorithms for Planar Graphs
by: Monika Rauch Henzinger, Philip N. Klein, Satish Rao, Sairam Subramanian v. 55 i. 1 p. 3 - 23
Natural Proofs
by: Alexander A. Razborov, Steven Rudich v. 55 i. 1 p. 24 - 35
Decision Tree Complexity and Betti Numbers
by: Andrew Chi-Chih Yao v. 55 i. 1 p. 36 - 43
Optimal Parallel Suffix Tree Construction
by: Ramesh Hariharan v. 55 i. 1 p. 44 - 69
The Discovery of Algorithmic Probability
by: Ray J. Solomonoff v. 55 i. 1 p. 73 - 88
Stochastic Complexity in Learning
by: Jorma Rissanen v. 55 i. 1 p. 89 - 95
Learning about the Parameter of the Bernoulli Model
by: V. G. Vovk v. 55 i. 1 p. 96 - 104
On-Line Maximum Likelihood Prediction with Respect to General Loss Functions
by: Kenji Yamanishi v. 55 i. 1 p. 105 - 118
A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
by: Yoav Freund, Robert E. Schapire v. 55 i. 1 p. 119 - 139
Characterizing Rational Versus Exponential learning Curves
by: Dale Schuurmans v. 55 i. 1 p. 140 - 160
Approximation and Learning of Convex Superpositions
by: Leonid Gurvits, Pascal Koiran v. 55 i. 1 p. 161 - 170
Learning Distributions by Their Density Levels: A Paradigm for Learning without a Teacher
by: Shai Ben-David, Michael Lindenbaum v. 55 i. 1 p. 171 - 182
Learning Recursive Functions from Approximations
by: John Case, Susanne Kaufmann, Efim B. Kinber, Martin Kummer v. 55 i. 1 p. 183 - 196
Dyn-FO: A Parallel, Dynamic Complexity Class
by: Sushant Patnaik, Neil Immerman v. 55 i. 2 p. 199 - 209
Bounded Arity Datalog (not-)Queries on Graphs
by: Foto N. Afrati v. 55 i. 2 p. 210 - 228
Relaxing the Uniformity and Independence Assumptions Using the Concept of Fractal Dimension
by: Christos Faloutsos, Ibrahim Kamel v. 55 i. 2 p. 229 - 240
Query Languages for Bags and Aggregate Functions
by: Leonid Libkin, Limsoon Wong v. 55 i. 2 p. 241 - 272
Finitely Representable Databases
by: Stéphane Grumbach, Jianwen Su v. 55 i. 2 p. 273 - 298
A Query Language for NC
by: Dan Suciu, Val Tannen v. 55 i. 2 p. 299 - 321
The Complexity of the Evaluation of Complex Algebra Expressions
by: Dan Suciu, Jan Paredaens v. 55 i. 2 p. 322 - 343
Relative Serializability: An Approach for Relaxing the Atomicity of Transactions
by: Vashudha Krishnaswamy, Divyakant Agrawal, John L. Bruno, Amr El Abbadi v. 55 i. 2 p. 344 - 354
Can Datalog Be Approximated?
by: Surajit Chaudhuri, Phokion G. Kolaitis v. 55 i. 2 p. 355 - 369
Efficient Oblivious Branching Programs for Threshold and Mod Functions
by: Rakesh K. Sinha, Jayram S. Thathachar v. 55 i. 3 p. 373 - 384
On the Design of Reliable Boolean Circuits That Contain Partially Unreliable Gates
by: Daniel J. Kleitman, Frank Thomson Leighton, Yuan Ma v. 55 i. 3 p. 385 - 401
(De)randomized Construction of Small Sample Spaces in NC
by: David R. Karger, Daphne Koller v. 55 i. 3 p. 402 - 413
An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution
by: Jeffrey C. Jackson v. 55 i. 3 p. 414 - 440
Size-Estimation Framework with Applications to Transitive Closure and Reachability
by: Edith Cohen v. 55 i. 3 p. 441 - 453
Maximum (s, t)-Flows in Planar Networks in O(|V|log|V|)-Time
by: Karsten Weihe v. 55 i. 3 p. 454 - 476
The Set of Minimal Words of a Context-Free Language is Context-Free
by: Jean Berstel, Luc Boasson v. 55 i. 3 p. 477 - 488
Logical Description of Contex-Free Graph Languages
by: Joost Engelfriet, Vincent van Oostrom v. 55 i. 3 p. 489 - 503
Amortization Results for Chromatic Search Trees, with an Application to Priority Queues
by: Joan Boyar, Rolf Fagerberg, Kim S. Larsen v. 55 i. 3 p. 504 - 521
Shared Global States in Distributed Computations
by: Eddy Fromentin, Michel Raynal v. 55 i. 3 p. 522 - 528
The Steiner Tree Problem in Orientation Metrics
by: G. Y. Yan, Andreas Alexander Albrecht, G. H. F. Young, Chak-Kuen Wong v. 55 i. 3 p. 529 - 546
Universally Serializable Computation
by: Lane A. Hemaspaandra, Mitsunori Ogihara v. 55 i. 3 p. 547 - 560

1996

Separator Based Sparsification. I. Planary Testing and Minimum Spanning Trees
by: David Eppstein, Zvi Galil, Giuseppe F. Italiano, Thomas H. Spencer v. 52 i. 1 p. 3 - 27
Parameterized Pattern Matching: Algorithms and Applications
by: Brenda S. Baker v. 52 i. 1 p. 28 - 42
Randomness is Linear in Space
by: Noam Nisan, David Zuckerman v. 52 i. 1 p. 43 - 52
Self-Routing Superconcentrators
by: Nicholas Pippenger v. 52 i. 1 p. 53 - 60
A Polynomial-Time Parsing Algorithm for K-Depth Languages
by: Alessandra Cherubini, Pierluigi San Pietro v. 52 i. 1 p. 61 - 79
On the Structural Properties of the Set of Fixpoints for Nondeterministic Recursive Definitions
by: Tsong Yueh Chen v. 52 i. 1 p. 80 - 86
Lower Bounds for the Union-Find and the Sp;it-Find Problem on Pointer Machines
by: Johannes A. La Poutré v. 52 i. 1 p. 87 - 99
A Framework for Testing Safety and Effective Computability
by: Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli v. 52 i. 1 p. 100 - 124
Semantic Representations and Query Labguages for Or-Sets
by: Leonid Libkin, Limsoon Wong v. 52 i. 1 p. 125 - 142
A Free Construction of Dynamic Terms
by: Egidio Astesiano, Elena Zucca v. 52 i. 1 p. 143 - 156
Applications of Range Query Theory to Relational Data Base Join and Selection Operations
by: Dan E. Willard v. 52 i. 1 p. 157 - 169
Finite Languages for the Representation of Finite Graphs
by: Andrzej Ehrenfeucht, Joost Engelfriet, Grzegorz Rozenberg v. 52 i. 1 p. 170 - 184
On Parikh Slender Languages and Power Series
by: Juha Honkala v. 52 i. 1 p. 185 - 190
Generic Separations
by: Lance Fortnow, Tomoyuki Yamakami v. 52 i. 1 p. 191 - 197
Learning Sparse Multivariate Polynomials over a Field with Queries and Counterexamples
by: Robert E. Schapire, Linda Sellie v. 52 i. 2 p. 201 - 213
On the Structure of Degrees of Inferability
by: Martin Kummer, Frank Stephan v. 52 i. 2 p. 214 - 238
General Bounds on the Number of Examples Needed for Learning Probabilistic Concepts
by: Hans-Ulrich Simon v. 52 i. 2 p. 239 - 254
Teaching a Smarter Learner
by: Sally A. Goldman, H. David Mathias v. 52 i. 2 p. 255 - 267
Asking Questions to Minimize Errors
by: Nader H. Bshouty, Sally A. Goldman, Thomas R. Hancock, Sleiman Matar v. 52 i. 2 p. 268 - 286
Temporal Interactions of Intervals in Distributed Systems
by: Ajay D. Kshemkalyani v. 52 i. 2 p. 287 - 298
Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files
by: Amihood Amir, Gary Benson, Martin Farach v. 52 i. 2 p. 299 - 307
Structural Average Case Complexity
by: Rainer Schuler, Tomoyuki Yamakami v. 52 i. 2 p. 308 - 348
On k-Dimensional Balanced Binary Trees
by: Vijay K. Vaishnavi v. 52 i. 2 p. 328 - 348
Exact Classification with Two-Layer Neural Nets
by: Gavin J. Gibson v. 52 i. 2 p. 349 - 356
On Instance-Completeness for Database Query Languages involving Object Creation
by: Marc Andries, Jan Paredaens v. 52 i. 2 p. 357 - 373
Learning Binary Perceptrons Perfectly Efficiently
by: Shao C. Fang, Santosh S. Venkatesh v. 52 i. 2 p. 374 - 389
The Intrinsic Complexity of Language Identification
by: Sanjay Jain, Arun Sharma v. 52 i. 3 p. 393 - 402
Inclusion Problems in Parallel Learning and Games
by: Martin Kummer, Frank Stephan v. 52 i. 3 p. 403 - 420
Oracles and Queries That Are Sufficient for Exact Learning
by: Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, Christino Tamon v. 52 i. 3 p. 421 - 433
Fat-Shattering and the Learnability of Real-Valued Functions
by: Peter L. Bartlett, Philip M. Long, Robert C. Williamson v. 52 i. 3 p. 434 - 452
Computing the Maximum Bichromatic Discrepancy with Applications to Computer Graphics and Machine Learning
by: David P. Dobkin, Dimitrios Gunopulos, Wolfgang Maass v. 52 i. 3 p. 453 - 470
Learning from a Consistently Ignorant Teacher
by: Michael Frazier, Sally A. Goldman, Nina Mishra, Leonard Pitt v. 52 i. 3 p. 471 - 492
Normal Forms and Conservative Extension Properties for Query Languages over Collection Types
by: Limsoon Wong v. 52 i. 3 p. 495 - 505
An Extension of Van Gelder's Alternating Fixpoint to Magic Programs
by: Shinichi Morishita v. 52 i. 3 p. 506 - 521
Completeness Results for Recursive Data Bases
by: Tirza Hirst, David Harel v. 52 i. 3 p. 522 - 536
Reflective Programming in the Relational Algebra
by: Jan Van den Bussche, Dirk Van Gucht, Gottfried Vossen v. 52 i. 3 p. 537 - 549
Selectivity and Cost Estimation for Joins Based on Random Sampling
by: Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Arun N. Swami v. 52 i. 3 p. 550 - 569
Towards Tractable Algebras for Bags
by: Stéphane Grumbach, Tova Milo v. 52 i. 3 p. 570 - 588
Indexing for Data Models with Constraints and Classes
by: Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter v. 52 i. 3 p. 589 - 612
An O(n) Algorithm for Abelian p-Group Isomorphism and an O(n log n) Algorithm for Abelian Group Isomorphism
by: Narayan Vikas v. 53 i. 1 p. 1 - 9
Automaticity I: Properties of a Measure of Descriptional Complexity
by: Jeffrey Shallit, Yuri Breitbart v. 53 i. 1 p. 10 - 25
Learnability: Admissible, Co-Finite, and Hypersimple Languages
by: Ganesh Baliga, John Case v. 53 i. 1 p. 26 - 32
Language Theoretic and Algorithmic Properties of d-dimensional Collages and Patterns in a Grid
by: Frank Drewes v. 53 i. 1 p. 33 - 66
Concurrent Counting
by: Shlomo Moran, Gadi Taubenfeld, Irit Yadin v. 53 i. 1 p. 61 - 78
New Lower Bounds and Hierarchy Results for Restricted Branching Programs
by: Detlef Sieling v. 53 i. 1 p. 79 - 87
Incremental Learning from Positive Data
by: Steffen Lange, Thomas Zeugmann v. 53 i. 1 p. 88 - 103
Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution
by: Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski v. 53 i. 1 p. 104 - 111
Towards Structured Parallel Computing on Architecture-Independent Parallel Algorithm Design for Distributed-Memory Architectures
by: Feng Gao v. 53 i. 1 p. 112 - 128
Efficient Theoretic and Practical Algorithms for Linear Matroid Intersection Problems
by: Harold N. Gabow, Ying Xu v. 53 i. 1 p. 129 - 147
A Space Efficient Variant of Path Copying for Partially Persistent Sorted Sets
by: Paul F. Dietz v. 53 i. 1 p. 148 - 152
Polynomial-Time Isomorphism of 1-L-Complete Sets
by: Manindra Agrawal, Somenath Biswas v. 53 i. 2 p. 155 - 160
On Limited Nondeterminism and the Complexity of the V-C Dimension
by: Christos H. Papadimitriou, Mihalis Yannakakis v. 53 i. 2 p. 161 - 170
On Closure Properties of #P in the Context of PF ° #P
by: Mitsunori Ogihara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe v. 53 i. 2 p. 171 - 179
Taking It to the Limit: On Infinite Variants of NP-Complete Problems
by: Tirza Hirst, David Harel v. 53 i. 2 p. 180 - 193
P-Selektive Sets and Reducing Search to Decision vs Self-Reducibility
by: Edith Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman v. 53 i. 2 p. 194 - 209
P-Selektive Self-Reducible Sets: A New Characterization of P
by: Harry Buhrman, Leen Torenvliet v. 53 i. 2 p. 210 - 217
Pointers versus Arithmetic in PRAMs
by: Patrick W. Dymond, Faith E. Fich, Naomi Nishimura, Prabhakar Ragde, Walter L. Ruzzo v. 53 i. 2 p. 218 - 232
Relative to a Random Oracle, NP Is Not Small
by: Steven M. Kautz, Peter Bro Miltersen v. 53 i. 2 p. 235 - 250
Multi-prover Encoding Schemes and Three-prover Proof Systems
by: Gábor Tardos v. 53 i. 2 p. 251 - 260
Random Strings Make Hard Instances
by: Harry Buhrman, Pekka Orponen v. 53 i. 2 p. 261 - 266
On the Isomorphism Conjecture for Weak Reducibilities
by: Manindra Agrawal v. 53 i. 2 p. 267 - 282
Logical Definability of Counting Functions
by: Kevin J. Compton, Erich Grädel v. 53 i. 2 p. 283 - 297
On the Query Complexity of Clique Size and Maximum Satisfiability
by: Richard Chang v. 53 i. 2 p. 298 - 313
Bounds on the Greedy Routing Algorithm for Array Networks
by: Michael Mitzenmacher v. 53 i. 3 p. 317 - 327
Improved Parity-Declustered Layouts for Disk Arrays
by: Eric J. Schwabe, Ian M. Sutherland v. 53 i. 3 p. 328 - 343
List Ranking and List Scan on the CRAY C90
by: Margaret Reid-Miller v. 53 i. 3 p. 344 - 356
Dynamic Load Balancing by Random Matchings
by: Bhaskar Ghosh, S. Muthukrishnan v. 53 i. 3 p. 357 - 370
Construction of the Mesh and the Torus Tolerating a Large Number of Faults
by: Hisao Tamaki v. 53 i. 3 p. 371 - 379
On the Parallel Complexity of Gaussian Elimination with Pivoting
by: Mauro Leoncini v. 53 i. 3 p. 380 - 394
An Optimal Randomised Logarithmic Time Connectivity Algorithm for the EREW PRAM
by: Shay Halperin, Uri Zwick v. 53 i. 3 p. 395 - 416
Efficient Low-Contention Parallel Algorithms
by: Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran v. 53 i. 3 p. 417 - 442
An Optimal Predicate Locking Scheduler
by: Carlo Meghini, Costantino Thanos v. 53 i. 3 p. 443 - 468
A Threshold for Unsatisfiability
by: Andreas Goerdt v. 53 i. 3 p. 469 - 486
Maximal and Minimal Solutions to Language Equations
by: Lila Kari, Gabriel Thierrin v. 53 i. 3 p. 487 - 496
The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions
by: Thomas Eiter, Georg Gottlob v. 53 i. 3 p. 497 - 512
K One-Way Heads Cannot Do String-Matching
by: Tao Jiang, Ming Li v. 53 i. 3 p. 513 - 524
River Routing with a Generalized Model
by: Jean R. S. Blair, Errol L. Lloyd v. 53 i. 3 p. 525 - 544
On Completeness Under Random Reductions
by: Suresh Chari, Pankaj Rohatgi v. 53 i. 3 p. 545 - 555
Regular Description of Context-Free Graph Languages
by: Joost Engelfriet, Vincent van Oostrom v. 53 i. 3 p. 556 - 574
Partition Triples: A Tool for Reduction of Data Sets
by: Jerzy W. Grzymala-Busse, Soe Than v. 53 i. 3 p. 575 - 582
Program Synthesis in the Presence of Infinite Number of Inaccuracies
by: Sanjay Jain v. 53 i. 3 p. 583 - 591

1995

On the Power of the Linear Array Architecture for Performing Tree-Structured Computations
by: Konstantinos Kalpakis, Yaacov Yesha v. 50 i. 1 p. 1 - 10
Polynomial Size Test Sets for Context-Free Languages
by: Juhani Karhumäki, Wojciech Plandowski, Wojciech Rytter v. 50 i. 1 p. 11 - 19
On the Complexity of Teaching
by: Sally A. Goldman, Michael J. Kearns v. 50 i. 1 p. 20 - 31
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes
by: Avrim Blum, Lisa Hellerstein, Nick Littlestone v. 50 i. 1 p. 32 - 40
On Learning Multiple Concepts in Parallel
by: Efim B. Kinber, Carl H. Smith, Mahendran Velauthapillai, Rolf Wiehagen v. 50 i. 1 p. 41 - 52
Decision Problems for Patterns
by: Tao Jiang, Arto Salomaa, Kai Salomaa, Sheng Yu v. 50 i. 1 p. 53 - 63
Load Sharing with Parallel Priority Queues
by: Ian Parberry v. 50 i. 1 p. 64 - 73
Characterizations of Learnability for Classes of {0, ..., n}-Valued Functions
by: Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler, Philip M. Long v. 50 i. 1 p. 74 - 86
On the Computational Complexity of Finite Cellular Automata
by: Klaus Sutner v. 50 i. 1 p. 87 - 87
Efficient Asynchronous Simulation of a Class of Synchronous Parallel Algorithms
by: Naomi Nishimura v. 50 i. 1 p. 98 - 113
Robust Trainability of Single Neurons
by: Klaus-Uwe Höffgen, Hans-Ulrich Simon, Kevin S. Van Horn v. 50 i. 1 p. 114 - 125
Single Row Routing on Multilayers
by: Adair Dingle, Ivan Hal Sudborough v. 50 i. 1 p. 126 - 131
On the Computational Power of Neural Nets
by: Hava T. Siegelmann, Eduardo D. Sontag v. 50 i. 1 p. 132 - 150
On the NP-Isomorphism Problem with Respect to Random Instances
by: Jie Wang, Jay Belanger v. 50 i. 1 p. 151 - 164
Implication Problems for Functional Constraints on Databases Supporting Complex Objects
by: Minoru Ito, Grant E. Weddell v. 50 i. 1 p. 165 - 187
PP Is Closed under Intersection
by: Richard Beigel, Nick Reingold, Daniel A. Spielman v. 50 i. 2 p. 191 - 202
Approximations and Optimal Geometric Divide-an-Conquer
by: Jirí Matousek v. 50 i. 2 p. 203 - 208
Testing Finite State Machines: Fault Detection
by: Mihalis Yannakakis, David Lee v. 50 i. 2 p. 209 - 227
Fast Approximation Algorithms for Multicommodity Flow Problems
by: Frank Thomson Leighton, Fillia Makedon, Serge A. Plotkin, Clifford Stein, Éva Stein, Spyros Tragoudas v. 50 i. 2 p. 228 - 243
Competitive Paging with Locality of Reference
by: Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber v. 50 i. 2 p. 244 - 258
A Matroid Approach to Finding Edge Connectivity and Packing Arborescences
by: Harold N. Gabow v. 50 i. 2 p. 259 - 273
Effective Noether Irreducibility Forms and Applications
by: Erich Kaltofen v. 50 i. 2 p. 274 - 295
Fast Monte Carlo Algorithms for Permutation Groups
by: László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, Ákos Seress v. 50 i. 2 p. 296 - 308
Computing with First-Order Logic
by: Serge Abiteboul, Victor Vianu v. 50 i. 2 p. 309 - 335
When Won't Membership Queries Help?
by: Dana Angluin, Michael Kharitonov v. 50 i. 2 p. 336 - 355
On Unique Satisfiability and the Threshold Behavior of Randomized Reductions
by: Richard Chang, Jim Kadin, Pankaj Rohatgi v. 50 i. 3 p. 359 - 373
Superlinear Lower Bounds for Bounded-Width Branching Programs
by: David A. Mix Barrington, Howard Straubing v. 50 i. 3 p. 374 - 381
Complexity Classes and Sparse Oracles
by: Daniel P. Bovet, Pierluigi Crescenzi, Riccardo Silvestri v. 50 i. 3 p. 382 - 390
Approximation Properties of NP Minimization Classes
by: Phokion G. Kolaitis, Madhukar N. Thakur v. 50 i. 3 p. 391 - 411
Closure Properties and Witness Reduction
by: Sanjay Gupta v. 50 i. 3 p. 412 - 432
Monotone Separation of Logarithmic Space from Logarithmic Depth
by: Michelangelo Grigni, Michael Sipser v. 50 i. 3 p. 433 - 437
Circuits, Matrices, and Nonassociative Computation
by: Martin Beaudry, Pierre McKenzie v. 50 i. 3 p. 441 - 455
The Power of the Middle Bit of a #P Function
by: Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, Jacobo Torán v. 50 i. 3 p. 456 - 467
Bounding the Complexity of Advice Functions
by: Ricard Gavaldà v. 50 i. 3 p. 468 - 475
Saving Queries with Randomness
by: Pankaj Rohatgi v. 50 i. 3 p. 476 - 492
Descriptive Complexity of #P Functions
by: Sanjeev Saluja, K. V. Subrahmanyam, Madhukar N. Thakur v. 50 i. 3 p. 493 - 505
Interactive Proof Systems with Polynomially Bounded Strategies
by: Anne Condon, Richard E. Ladner v. 50 i. 3 p. 506 - 518
Learning Boolean Read-Once Formulas over Generalized Bases
by: Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein v. 50 i. 3 p. 521 - 542
An O(n^(log log n)) Learning Algorithm for DNT under the Uniform Distribution
by: Yishay Mansour v. 50 i. 3 p. 543 - 550
On Weak Learning
by: David P. Helmbold, Manfred K. Warmuth v. 50 i. 3 p. 551 - 573
Breaking the Probability 1/2 Barrier in FIN-Type Learning
by: Robert P. Daley, Bala Kalyanasundaram, Mahendran Velauthapillai v. 50 i. 3 p. 574 - 599
Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution
by: Michael Kharitonov v. 50 i. 3 p. 600 - 610
Editor's Forword
by: Yehoshua Sagiv v. 51 i. 1 p. 1 - 1
Handling Infinite Temporal Data
by: F. Kabanza, J.-M. Stevenne, Pierre Wolper v. 51 i. 1 p. 3 - 17
Query Size Estimation by Adaptive Sampling
by: Richard J. Lipton, Jeffrey F. Naughton v. 51 i. 1 p. 18 - 25
Constraint Query Languages
by: Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz v. 51 i. 1 p. 26 - 52
Constrained Shared Locks for Increased Concurrency in Databases
by: Divyakant Agrawal, Amr El Abbadi v. 51 i. 1 p. 53 - 63
The Expressive Powers of the Logic Programming Semantics
by: John S. Schlipf v. 51 i. 1 p. 64 - 86
On the Efficiency of Transforming Database Logic Programs
by: Yatin P. Saraiya v. 51 i. 1 p. 87 - 109
On the Expressive Power of Datalog: Tools and a Case Study
by: Phokion G. Kolaitis, Moshe Y. Vardi v. 51 i. 1 p. 110 - 134
Editor's Foreword
by: Alberto O. Mendelzon v. 51 i. 2 p. 135 - 135
On the Expected Size of Recursive Datalog Queries
by: S. Seshadri, Jeffrey F. Naughton v. 51 i. 2 p. 137 - 148
Tractable Query Languages for Complex Object Databases
by: Stéphane Grumbach, Victor Vianu v. 51 i. 2 p. 149 - 167
A Tight Upper Bound on the Benefits of Replica Control Protocols
by: Donald B. Johnson, Larry Raab v. 51 i. 2 p. 168 - 176
On Datalog vs. Polynomial Time
by: Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis v. 51 i. 2 p. 177 - 196
Spatial Query Optimization: From Boolean Constraints to Range Queries
by: Richard Helm, Kim Marriott, Martin Odersky v. 51 i. 2 p. 197 - 210
Non-deterministic Queue Operations
by: Hector Garcia-Molina, Kenneth Salem v. 51 i. 2 p. 211 - 222
Subtyping in OODBs
by: Catriel Beeri, Tova Milo v. 51 i. 2 p. 223 - 243
Extrema Predicates in Deductive Databases
by: Sumit Ganguly, Sergio Greco, Carlo Zaniolo v. 51 i. 2 p. 244 - 259
Clique Partitions, Graph Compression and Speeding-Up Algorithms
by: Tomás Feder, Rajeev Motwani v. 51 i. 2 p. 261 - 272
Language Learning with Some Negative Information
by: Ganesh Baliga, John Case, Sanjay Jain v. 51 i. 2 p. 273 - 285
The Expected Advantage of Asynchrony
by: Richard L. Cole, Ofer Zajicek v. 51 i. 2 p. 286 - 300
Editor's Foreword
by: Wolfgang Maass v. 51 i. 3 p. 339 - 339
Competitive Algorithms for Distributed Data Management
by: Yair Bartal, Amos Fiat, Yuval Rabani v. 51 i. 3 p. 341 - 358
New Algorithms for an Ancient Scheduling Problem
by: Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra v. 51 i. 3 p. 359 - 366
Fast Learning of k-Term DNF Formulas with Queries
by: Avrim Blum, Steven Rudich v. 51 i. 3 p. 367 - 373
Planar Separators and Parallel Polygon Triangulation
by: Michael T. Goodrich v. 51 i. 3 p. 374 - 389
Entropy and Sorting
by: Jeff Kahn, Jeong Han Kim v. 51 i. 3 p. 390 - 399
On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs
by: Raimund Seidel v. 51 i. 3 p. 400 - 403
Complexity Tailored Design: A New Design Methodology for Databases With Incomplete Information
by: Tomasz Imielinski, Ron van der Meyden, Kumar V. Vadaparty v. 51 i. 3 p. 405 - 432
Method Schemas
by: Serge Abiteboul, Paris C. Kanellakis, Sridhar Ramaswamy, Emmanuel Waller v. 51 i. 3 p. 433 - 455
On Comparison and Analysis of Algorithms for Multiplication in GF(2^m)
by: Changho Seo, Jongin Lim, Hichum Eun v. 51 i. 3 p. 456 - 459
Continuous Algebras Revisited
by: Jirí Adámek, Evelyn Nelson, Jan Reiterman v. 51 i. 3 p. 460 - 471
Emptiness Problems of eNCE Graph Languages
by: Konstantin Skodinis, Egon Wanke v. 51 i. 3 p. 472 - 485
The Best Nondeterministic Representations of Finite Orderings
by: Camino R. Vela, Antonio Bahamonde v. 51 i. 3 p. 486 - 494
Decision Trees with Boolean Threshold Queries
by: Yosi Ben-Asher, Ilan Newman v. 51 i. 3 p. 495 - 502
An O(n log log n) Time Algorithm for Constructing a Graph of Maximum Connectivity with Prescribed Degrees
by: Takao Asano v. 51 i. 3 p. 503 - 510
A Dichotomy Theorem for Maximum Generalized Satisfiability Problems
by: Nadia Creignou v. 51 i. 3 p. 511 - 522
On the Feasibility of Checking Temporal Integrity Constraints
by: Jan Chomicki, Damian Niwinski v. 51 i. 3 p. 523 - 535

1994

Three One-Way Heads Cannot Do String Matching
by: Mihály Geréb-Graus, Ming Li v. 48 i. 1 p. 1 - 8
Unique Complements and Decomposition of Database Schemata
by: Stephen J. Hegner v. 48 i. 1 p. 9 - 57
Hypergraph Languages of Bounded Degree
by: Joost Engelfriet, Linda Heyker v. 48 i. 1 p. 58 - 89
Parallel Solutions to Geometric Problems in the Scan Model of Computation
by: Guy E. Blelloch, James J. Little v. 48 i. 1 p. 90 - 115
Gap-Definable Counting Classes
by: Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz v. 48 i. 1 p. 116 - 148
Reversibility and Surjectivity Problems of Cellular Automata
by: Jarkko Kari v. 48 i. 1 p. 149 - 182
PSPACE Is Provable by Two Provers in One Round
by: Jin-yi Cai, Anne Condon, Richard J. Lipton v. 48 i. 1 p. 183 - 193
Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely)
by: Noga Alon, Pavel Pudlák v. 48 i. 1 p. 194 - 202
Learning Fixed Point Patterns by Recurrent Networks
by: Leong Kwan Li v. 48 i. 2 p. 203 - 213
Finding Level-Ancestors in Trees
by: Omer Berkman, Uzi Vishkin v. 48 i. 2 p. 214 - 230
Exact Lower Time Bounds for Computing Boolean Functions on CREW PRAMs
by: Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk v. 48 i. 2 p. 231 - 254
The Complexity of Propositional Closed World Reasoning and Circumscription
by: Marco Cadoli, Maurizio Lenzerini v. 48 i. 2 p. 255 - 310
Nonuniform Learnability
by: Gyora M. Benedek, Alon Itai v. 48 i. 2 p. 311 - 323
On Reductions of NP Sets to Sparse Sets
by: Steven Homer, Luc Longpré v. 48 i. 2 p. 324 - 336
Combinatorial Techniques for Universal Hashing
by: Douglas R. Stinson v. 48 i. 2 p. 337 - 346
On the Perceptron Learning Algorithm on Data with High Precision
by: Kai-Yeung Siu, Amir Dembo, Thomas Kailath v. 48 i. 2 p. 347 - 356
A Taxonomy of Complexity Classes of Functions
by: Alan L. Selman v. 48 i. 2 p. 357 - 381
Provably Good Mesh Generation
by: Marshall W. Bern, David Eppstein, John R. Gilbert v. 48 i. 3 p. 384 - 409
Competitive k-Server Algorithms
by: Amos Fiat, Yuval Rabani, Yiftach Ravid v. 48 i. 3 p. 410 - 428
Specified Precision Polynomial Root Isolation Is in NC
by: C. Andrew Neff v. 48 i. 3 p. 429 - 463
Efficient Distribution-Free Learning of Probabilistic Concepts
by: Michael J. Kearns, Robert E. Schapire v. 48 i. 3 p. 464 - 497
On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence
by: Christos H. Papadimitriou v. 48 i. 3 p. 498 - 532
Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths
by: Michael L. Fredman, Dan E. Willard v. 48 i. 3 p. 533 - 551
Simple Characterizations of P(#P) and Complete Problems
by: Seinosuke Toda v. 49 i. 1 p. 1 - 17
Group Structured Linear Cellular Automata over Zm
by: Tadakazu Sato v. 49 i. 1 p. 18 - 23
The Random Oracle Hypothesis Is False
by: Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, Pankaj Rohatgi v. 49 i. 1 p. 24 - 39
Time-Extraction for Temporal Logic-Logic Programming and Local Process Time
by: Takashi Hattori v. 49 i. 1 p. 40 - 56
The Complexity of Connectivity Problems on Context-Free Graph Languages
by: Egon Wanke v. 49 i. 1 p. 57 - 82
Symmetry in Self-Correcting Cellular Automata
by: Nicholas Pippenger v. 49 i. 1 p. 83 - 95
Characterizing Language Identification by Standardizing Operations
by: Sanjay Jain, Arun Sharma v. 49 i. 1 p. 96 - 107
Bounded Degree Graph Inference from Walks
by: Vijay V. Raghavan v. 49 i. 1 p. 108 - 132
A Kleene-like Characterization of Languages Accepted by Systolic Tree Automata
by: Emanuela Fachini, Angelo Monti v. 49 i. 1 p. 133 - 147
Hardness vs Randomness
by: Noam Nisan, Avi Wigderson v. 49 i. 2 p. 149 - 167
Invariant Sets for Substitution
by: Taishin Y. Nishida, Youichi Kobuchi v. 49 i. 2 p. 168 - 174
On Computing Serial Dependency Relations
by: Narayanan Krishnakumar v. 49 i. 2 p. 175 - 188
Vacillatory Learning of Nearly Minimal Size Grammars
by: John Case, Sanjay Jain, Arun Sharma v. 49 i. 2 p. 189 - 207
Dynamic Dictionary Matching
by: Amihood Amir, Martin Farach, Zvi Galil, Raffaele Giancarlo, Kunsoo Park v. 49 i. 2 p. 208 - 222
A Branching Time Logic with Past Operators
by: Michael Kaminski v. 49 i. 2 p. 223 - 246
Non-Deterministic Communication Complexity with Few Witnesses
by: Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson v. 49 i. 2 p. 247 - 257
The Translation Power of Top-Down Tree-to-Graph Transducers
by: Joost Engelfriet, Heiko Vogler v. 49 i. 2 p. 258 - 305
Efficient Inference of Partial Types
by: Dexter Kozen, Jens Palsberg, Michael I. Schwartzbach v. 49 i. 2 p. 306 - 324
A Linear-Time Near-Optimum-Length Triangulation Algorithm for Convex Polygons
by: Vitit Kantabutra v. 49 i. 2 p. 325 - 333
A Three-Valued Semantics for Deductive Databases and Logic Programs
by: Jia-Huai You, Li-Yan Yuan v. 49 i. 2 p. 334 - 361
Measures of Nondeterminism for Pushdown Automata
by: Kai Salomaa, Sheng Yu v. 49 i. 2 p. 362 - 374
Learning with Discrete Multi-valued Neurons
by: Zoran Obradovic, Ian Parberry v. 49 i. 2 p. 375 - 390
Robust Gift Wrapping for the Three-Dimensional Convex Hull
by: Kokichi Sugihara v. 49 i. 2 p. 391 - 407
Listing Graphs That Satisfy First-Order Sentences
by: Leslie Ann Goldberg v. 49 i. 2 p. 408 - 424
An Efficient Algorithm for Hidden Surface Removal, II
by: Ketan Mulmuley v. 49 i. 3 p. 427 - 453
Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry
by: Bonnie Berger, John Rompel, Peter W. Shor v. 49 i. 3 p. 454 - 477
The Probabilistic Method Yields Deterministic Parallel Algorithms
by: Rajeev Motwani, Joseph Naor, Moni Naor v. 49 i. 3 p. 478 - 516
Planarity Testing in Parallel
by: Vijaya Ramachandran, John H. Reif v. 49 i. 3 p. 517 - 561
Datalog vs First-Order Logic
by: Miklós Ajtai, Yuri Gurevich v. 49 i. 3 p. 562 - 588
Open Problems in "Systems That Learn"
by: Mark A. Fulk, Sanjay Jain, Daniel N. Osherson v. 49 i. 3 p. 589 - 604
On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line
by: Jin-yi Cai, Juris Hartmanis v. 49 i. 3 p. 605 - 619
Another Look at Parameterization for Order-Sorted Algebraic Specifications
by: Zhenyu Qian v. 49 i. 3 p. 620 - 666
Efficient Rebalancing of Chromatic Search Trees
by: Joan Boyar, Kim S. Larsen v. 49 i. 3 p. 667 - 682
The Nested Universal Relation Data Model
by: Mark Levene, George Loizou v. 49 i. 3 p. 683 - 717
The Surjectivity Problem for 2D Cellular Automata
by: Bruno Durand v. 49 i. 3 p. 718 - 725
Implication Problems for Functional Constraints on Databases Supporting Complex Objects
by: Minoru Ito, Grant E. Weddell v. 49 i. 3 p. 726 - 768
On Search, Decision, and the Efficiency of Polynomial-Time Algorithms
by: Michael R. Fellows, Michael A. Langston v. 49 i. 3 p. 769 - 779

1993

Normal and Sinkless Petri Nets
by: Rodney R. Howell, Louis E. Rosier, Hsu-Chun Yen v. 46 i. 1 p. 1 - 26
The Interconnection Problem
by: Klaus Jansen v. 46 i. 1 p. 27 - 38
Variable Precision Rough Set Model
by: Wojciech Ziarko v. 46 i. 1 p. 39 - 59
Computation Graphs for Actor Grammars
by: Dirk Janssens, M. Lens, Grzegorz Rozenberg v. 46 i. 1 p. 60 - 90
A Minimum 3-Connectivity Augmentation of a Graph
by: Toshimasa Watanabe, Akira Nakamura v. 46 i. 1 p. 91 - 127
Threshold Circuits of Bounded Depth
by: András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán v. 46 i. 2 p. 129 - 154
Deterministic Soliton Automata with at Most One Cycle
by: Jürgen Dassow, Helmut Jürgensen v. 46 i. 2 p. 155 - 197
Directed Drift: A New Linear Threshold Algorithm for Learning Binary Weights On-Line
by: Santosh S. Venkatesh v. 46 i. 2 p. 198 - 217
Handle-Rewriting Hypergraph Grammars
by: Bruno Courcelle, Joost Engelfriet, Grzegorz Rozenberg v. 46 i. 2 p. 218 - 270
On the Expressive Power of Temporal Logic
by: Joëlle Cohen, Dominique Perrin, Jean-Eric Pin v. 46 i. 3 p. 271 - 294
A Complexity Theory for Feasible Closure Properties
by: Mitsunori Ogiwara, Lane A. Hemachandra v. 46 i. 3 p. 295 - 325
Graph Theoretic Analysis of PLA Folding Heuristics
by: S. S. Ravi, Errol L. Lloyd v. 46 i. 3 p. 326 - 348
A Note on Bi-immunity and p-Closeness of p-Cheatable Sets in P/Poy
by: Judy Goldsmith, Deborah Joseph, Paul Young v. 46 i. 3 p. 349 - 362
Collapsing Degrees via Strong Computation
by: Lane A. Hemachandra, Albrecht Hoene v. 46 i. 3 p. 363 - 380
Matrix and Matricial Iteration Theories, Part I
by: Stephen L. Bloom, Zoltán Ésik v. 46 i. 3 p. 381 - 408
Matrix and Matricial Iteration Theories, Part II
by: Stephen L. Bloom, Zoltán Ésik v. 46 i. 3 p. 409 - 439
Editor's Foreword: Selected Papers of PODS 1989
by: Ashok K. Chandra v. 47 i. 1 p. 1 - 1
Why a Single Parallelization Strategy Is Not Enough in Knowledge Bases
by: Simona Rabinovichi Cohen, Ouri Wolfson v. 47 i. 1 p. 2 - 44
B-Trees with Inserts and Deletes: Why Free-at-Empty Is Better Than Merge-at-Half
by: Theodore Johnson, Dennis Shasha v. 47 i. 1 p. 45 - 76
A Logic Programming with Complex Objects
by: Michael Kifer, James Wu v. 47 i. 1 p. 77 - 120
Algebraic and Calculus Query Languages for Recursively Typed Complex Objects
by: Richard Hull, Jianwen Su v. 47 i. 1 p. 121 - 156
The Impact of Recovery on Concurrency Control
by: William E. Weihl v. 47 i. 1 p. 157 - 184
The Alternating Fixpoint of Logic Programs with Negation
by: Allen Van Gelder v. 47 i. 1 p. 185 - 221
Logical Query Optimization by Proff-Tree Transformation
by: Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi v. 47 i. 1 p. 222 - 248
Removing Randomness in Parallel Computation without a Processor Penalty
by: Michael Luby v. 47 i. 2 p. 250 - 286
Nonexpressibility of Fairness and Signaling
by: David A. McAllester, Prakash Panangaden, Vasant Shanbhogue v. 47 i. 2 p. 287 - 321
Communication Complexity and Combinatorial Lattice Theory
by: László Lovász, Michael E. Saks v. 47 i. 2 p. 322 - 349
Effect of Connectivity in an Associative Memory Model
by: János Komlós, Ramamohan Paturi v. 47 i. 2 p. 350 - 373
The Discrete Logarithm Modulo a Composite Hides O(n) Bits
by: Johan Håstad, A. W. Schrift, Adi Shamir v. 47 i. 3 p. 376 - 404
Functions with Bounded Symmetric Communication Complexity, Programs over Commutative Monoids, and ACC
by: Mario Szegedy v. 47 i. 3 p. 405 - 423
Surpassing the Information Theoretic Bound with Fusion Trees
by: Michael L. Fredman, Dan E. Willard v. 47 i. 3 p. 424 - 436
Output Sensitive and Dynamic Constructions of Higher Order Voronoi Diagrams and Levels in Arrangements
by: Ketan Mulmuley v. 47 i. 3 p. 437 - 458
Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs
by: Ming-Yang Kao, Philip N. Klein v. 47 i. 3 p. 459 - 500
Deterministic Sorting in Nearly Logarithmic Time on the Hypercube and Related Computers
by: Robert Cypher, C. Greg Plaxton v. 47 i. 3 p. 501 - 548
Self-Testing/Correcting with Applications to Numerical Problems
by: Manuel Blum, Michael Luby, Ronitt Rubinfeld v. 47 i. 3 p. 549 - 595

1992

Connection-Trap-Free Database Schemes
by: Edward P. F. Chan, Paolo Atzeni v. 44 i. 1 p. 1 - 22
Contraction Algebras and Unification of (Infinite) Terms
by: Razvan Diaconescu v. 44 i. 1 p. 23 - 42
Parallel Restructuring and Evaluation of Expressions
by: David E. Muller, Franco P. Preparata v. 44 i. 1 p. 43 - 62
The Correlation between the Complexities of the Nonhierarchical and Hierarchical Versions of Graph Problems
by: Thomas Lengauer, Klaus W. Wagner v. 44 i. 1 p. 63 - 93
Perfect Matching for Regular Graphs is AC°-Hard for the General Matching Problem
by: Elias Dahlhaus, Marek Karpinski v. 44 i. 1 p. 94 - 102
Processor-Time Tradeoffs in PRAM Simulations
by: Prabhakar Ragde v. 44 i. 1 p. 103 - 113
Self-Similarity of Linear Cellular Automata
by: Satoshi Takahashi v. 44 i. 1 p. 114 - 140
Undecidability of Safety for the Schematic Protection Model with Cyclic Creates
by: Ravi S. Sandhu v. 44 i. 1 p. 141 - 159
Some Remarks on a Theorem of Sakarovitch
by: Thomas Herbst v. 44 i. 1 p. 160 - 165
The Complexity Types of Computable Sets
by: Wolfgang Maass, Theodore A. Slaman v. 44 i. 2 p. 168 - 192
On the Theory of Average Case Complexity
by: Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby v. 44 i. 2 p. 193 - 219
Almost Everywhere High Nonuniform Complexity
by: Jack H. Lutz v. 44 i. 2 p. 220 - 258
Multi-Oracle Interactive Protocols with Constant Space Verifiers
by: Uriel Feige, Adi Shamir v. 44 i. 2 p. 259 - 271
Turing Machines with Few Accepting Computations and Low Sets for PP
by: Johannes Köbler, Uwe Schöning, Seinosuke Toda, Jacobo Torán v. 44 i. 2 p. 272 - 286
Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography
by: Steven Homer, Alan L. Selman v. 44 i. 2 p. 287 - 301
The Complexity of Circuit Value and Network Stability
by: Ernst W. Mayr, Ashok Subramanian v. 44 i. 2 p. 302 - 323
Results on Communication Complexity Classes
by: Tak Wah Lam, Walter L. Ruzzo v. 44 i. 2 p. 324 - 342
Inductive Reasoning and Kolmogorov Complexity
by: Ming Li, Paul M. B. Vitányi v. 44 i. 2 p. 343 - 384
The Invariant Problem for Binary String Structures and the Parallel Complexity Theory of Queries
by: Steven Lindell v. 44 i. 3 p. 385 - 410
Distributed Event Algebras
by: Andrew Klapper v. 44 i. 3 p. 411 - 424
Finite Automata on Directed Graphs
by: Michael Kaminski, Shlomit S. Pinter v. 44 i. 3 p. 425 - 446
B-Fairness and Structural B-Fairness in Petri Net Models of Concurrent Systems
by: Manuel Silva, Tadao Murata v. 44 i. 3 p. 447 - 477
Regular Languages in NC¹
by: David A. Mix Barrington, Kevin J. Compton, Howard Straubing, Denis Thérien v. 44 i. 3 p. 478 - 499
On Polynomial Time One-Truth-Table Reducibility to a Sparse Set
by: Osamu Watanabe v. 44 i. 3 p. 500 - 516
Discrete-Time versus Continuous-Time Models of Neural Networks
by: Xin Wang, Edward K. Blum v. 45 i. 1 p. 1 - 19
Feedforward Nets for Interpolation and Classification
by: Eduardo D. Sontag v. 45 i. 1 p. 20 - 48
An Approximation Theorem for Topological Lambda Models and the Topological Incompleteness of Lambda Calculus
by: Furio Honsell, Simona Ronchi Della Rocca v. 45 i. 1 p. 49 - 75
The Powerset Algebra as a Natural Tool to Handle Nested Database Relations
by: Marc Gyssens, Dirk Van Gucht v. 45 i. 1 p. 76 - 103
On the Time-Complexity of Broadcast in Multi-hop Radio Networks: An Exponential Gap Between Determinism and Randomization
by: Reuven Bar-Yehuda, Oded Goldreich, Alon Itai v. 45 i. 1 p. 104 - 126
Using the Hamiltonian Path Operator to Capture NP
by: Iain A. Stewart v. 45 i. 1 p. 127 - 151
Positional Simulation of Two-Way Automata: Proof of a Conjecture of R. Kannan and Generalizations
by: Jean-Camille Birget v. 45 i. 2 p. 154 - 179
Lower Bounds on the Length of Universal Traversal Sequences
by: Allan Borodin, Walter L. Ruzzo, Martin Tompa v. 45 i. 2 p. 180 - 203
Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs
by: László Babai, Noam Nisan, Mario Szegedy v. 45 i. 2 p. 204 - 232
A New Fixed Point Approach for Stable Networks and Stable Marriages
by: Tomás Feder v. 45 i. 2 p. 233 - 284
Minimum-Complexity Pairing Functions
by: Kenneth W. Regan v. 45 i. 3 p. 285 - 295
Trade-Offs between Communication and Space
by: Tak Wah Lam, Prasoon Tiwari, Martin Tompa v. 45 i. 3 p. 296 - 315
Closure of Varieties of Languages under Products with Counter
by: Pascal Weil v. 45 i. 3 p. 316 - 339
Embedding Grids into Hypercubes
by: Saïd Bettayeb, Zevi Miller, Ivan Hal Sudborough v. 45 i. 3 p. 340 - 366
Foreground Automata
by: Ian F. Carlstrom v. 45 i. 3 p. 367 - 384
Nondiamond Theorems for Polynomial Time Reducibility
by: Rodney G. Downey v. 45 i. 3 p. 385 - 395
Models of a K-Rational Identity System
by: Daniel Krob v. 45 i. 3 p. 396 - 434
Design of Desirable Relational Database Schemes
by: Li-Yan Yuan, Z. Meral Özsoyoglu v. 45 i. 3 p. 435 - 470
Computing with Discrete Multi-Valued Neurons
by: Zoran Obradovic, Ian Parberry v. 45 i. 3 p. 471 - 492
Some Investigations on FCFS Scheduling in Hard Real Time Applications
by: Ulrich Schmid, Johann Blieberger v. 45 i. 3 p. 493 - 512

1991

On Denotational versus Predicative Semantics
by: Manfred Broy, Christian Lengauer v. 42 i. 1 p. 1 - 29
Realistic Analysis of Some Randomized Algorithms
by: Eric Bach v. 42 i. 1 p. 30 - 53
Unification Modulo an Equality Theory for Equational Logic Programming
by: Jia-Huai You v. 42 i. 1 p. 54 - 75
Relativized Counting Classes: Relations among Thresholds, Parity, and Mods
by: Richard Beigel v. 42 i. 1 p. 76 - 96
Some Lower Bound Results for Decentralized Extrema-Finding in Rings of Processors
by: Hans L. Bodlaender v. 42 i. 1 p. 97 - 118
Resource Bounds for Parallel Computation of Threshold and Symmetric Functions
by: Ming Li, Yaacov Yesha v. 42 i. 1 p. 119 - 137
Kernel-LEAF: A Logic plus Functional Language
by: Elio Giovannetti, Giorgio Levi, Corrado Moiso, Catuscia Palamidessi v. 42 i. 2 p. 139 - 185
Overlaps in Free Partially Commutative Monoids
by: Friedrich Otto, Celia Wrathall v. 42 i. 2 p. 186 - 198
One-Sided Recursions
by: Jeffrey F. Naughton v. 42 i. 2 p. 199 - 236
On Isomorphism Testing of a Class of 2-Nilpotent Groups
by: Max H. Garzon, Yechezkel Zalcstein v. 42 i. 2 p. 237 - 248
Corrigendum: Topologically Sweeping an Arrangement
by: Herbert Edelsbrunner, Leonidas J. Guibas v. 42 i. 2 p. 249 - 251
Two Lower Bounds in Asynchronous Distributed Computation
by: Pavol Duris, Zvi Galil v. 42 i. 3 p. 254 - 266
Lower Bounds to Randomized Algorithms for Graph Properties
by: Andrew Chi-Chih Yao v. 42 i. 3 p. 267 - 287
Improved Algorithms for Graph Four-Connectivity
by: Arkady Kanevsky, Vijaya Ramachandran v. 42 i. 3 p. 288 - 306
How to Emulate Shared Memory
by: Abhiram G. Ranade v. 42 i. 3 p. 307 - 326
Statistical Zero-Knowledge Languages can be Recognized in Two Rounds
by: William Aiello, Johan Håstad v. 42 i. 3 p. 327 - 345
Average Case Completeness
by: Yuri Gurevich v. 42 i. 3 p. 346 - 398
Transaction Synchronisation in Object Bases
by: Thanasis Hadzilacos, Vassos Hadzilacos v. 43 i. 1 p. 2 - 24
Hybrid Concurrency Control for Abstract Data Types
by: Maurice Herlihy, William E. Weihl v. 43 i. 1 p. 25 - 61
Datalog Extensions for Database Queries and Updates
by: Serge Abiteboul, Victor Vianu v. 43 i. 1 p. 62 - 124
Why not Negation by Fixpoint?
by: Phokion G. Kolaitis, Christos H. Papadimitriou v. 43 i. 1 p. 125 - 144
A Counting Algorithm for a Cyclic Binary Query
by: Ramsey W. Haddad, Jeffrey F. Naughton v. 43 i. 1 p. 145 - 169
A Semantics for Complex Objects and Approximate Answers
by: Peter Buneman, Susan B. Davidson, Aaron Watters v. 43 i. 1 p. 170 - 218
On the Expressive Power of Database Queries with Intermediate Types
by: Richard Hull, Jianwen Su v. 43 i. 1 p. 219 - 267
Time-Space Tradeoffs for Algebraic Problems on General Sequential Machines
by: Karl R. Abrahamson v. 43 i. 2 p. 269 - 289
A Lower Bound for Radio Broadcast
by: Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg v. 43 i. 2 p. 290 - 298
Learning Regular Languages from Counterexamples
by: Oscar H. Ibarra, Tao Jiang v. 43 i. 2 p. 299 - 316
Oblivious Routing with Limited Buffer Capacity
by: Danny Krizanc v. 43 i. 2 p. 317 - 327
The String Generating Power of Context-Free Hypergraph Grammars
by: Joost Engelfriet, Linda Heyker v. 43 i. 2 p. 328 - 360
An Axiomatic Approach to Voronoi-Diagrams in 3D
by: Sabine Stifter v. 43 i. 2 p. 361 - 379
Properties that Characterize LOGCFL
by: H. Venkateswaran v. 43 i. 2 p. 380 - 404
An Implicit Data Structure for Searching a Multikey Table in Logarithmic Time
by: Amos Fiat, J. Ian Munro, Moni Naor, Alejandro A. Schäffer, Jeanette P. Schmidt, Alan Siegel v. 43 i. 3 p. 406 - 424
Optimization, Approximation, and Complexity Classes
by: Christos H. Papadimitriou, Mihalis Yannakakis v. 43 i. 3 p. 425 - 440
Expressing Combinatorial Optimization Problems by Linear Programs
by: Mihalis Yannakakis v. 43 i. 3 p. 441 - 466
Program Structures: Some New Characterisations
by: Norman E. Fenton, R. W. Whitty v. 43 i. 3 p. 467 - 483
Outfix and Infix Codes and Related Classes of Languages
by: M. Ito, Helmut Jürgensen, Huei-Jan Shyr, Gabriel Thierrin v. 43 i. 3 p. 484 - 508
On Computing Decision Regions with Neural Nets
by: Leong Kwan Li v. 43 i. 3 p. 509 - 512

1990

Geometric Consistency Theorem for a Symbolic Perturbation Scheme
by: Chee-Keng Yap v. 40 i. 1 p. 2 - 18
Covering Orthogonal Polygons with Star Polygons: The Perfect Graph Approach
by: Rajeev Motwani, Arvind Raghunathan, Huzur Saran v. 40 i. 1 p. 19 - 48
Hidden Surface Removal for Rectangles
by: Marshall W. Bern v. 40 i. 1 p. 49 - 69
Applied Computational Geometry: Towards Robust Solutions of Basic Problems
by: David P. Dobkin, Deborah Silver v. 40 i. 1 p. 70 - 87
On Maximum Flows in Polyhedral Domains
by: Joseph S. B. Mitchell v. 40 i. 1 p. 88 - 123
The Hoare and Smith Power Domain Constructors Commute under Composition
by: Kevin E. Flannery, Johannes J. Martin v. 40 i. 2 p. 125 - 135
First-Order Spectra with One Variable
by: Etienne Grandjean v. 40 i. 2 p. 136 - 153
Soliton Automata
by: Jürgen Dassow, Helmut Jürgensen v. 40 i. 2 p. 154 - 181
Genomorphisms of Semi-Modular Lattices
by: Damas P. Gruska v. 40 i. 2 p. 182 - 187
Edge-Label Controlled Graph Grammars
by: Michael G. Main, Grzegorz Rozenberg v. 40 i. 2 p. 188 - 228
Parametrization for Order-Sorted Algebraic Specification
by: Axel Poigné v. 40 i. 2 p. 229 - 268
On the Power of Safe Locking
by: Georg Lausen, Eljas Soisalon-Soininen, Peter Widmayer v. 40 i. 2 p. 269 - 288
Picture Iteration and Picture Ambiguity
by: Changwook Kim v. 40 i. 3 p. 289 - 306
Boundary Graph Grammars with Dynamic Edge Relabeling
by: Joost Engelfriet, George Leih, Emo Welzl v. 40 i. 3 p. 307 - 345
Input-Dependent-Only Object Histories
by: Seymour Ginsburg, Dan Tian v. 40 i. 3 p. 346 - 375
The Complexity of Regular DNLC Graph Languages
by: IJsbrand Jan Aalbersberg, Joost Engelfriet, Grzegorz Rozenberg v. 40 i. 3 p. 376 - 404
On Inference Control in Semantic Data Models for Statistical Databases
by: Gultekin Özsoyoglu, Tzong-An Su v. 40 i. 3 p. 405 - 443
A Note on A.E. h-Complex Functions
by: Mark A. Fulk v. 40 i. 3 p. 444 - 449
Decomposing a Relation into a Tree of Binary Relations
by: Rina Dechter v. 41 i. 1 p. 2 - 24
A New Interpretation for Null Values in the Weak Instance Model
by: Paolo Atzeni, Maria Cristina De Bernardis v. 41 i. 1 p. 25 - 43
Logic Programming with Sets
by: Gabriel M. Kuper v. 41 i. 1 p. 44 - 64
Commutativity-Based Locking for Nested Transactions
by: Alan Fekete, Nancy A. Lynch, Michael Merritt, William E. Weihl v. 41 i. 1 p. 65 - 156
Bounds on the Propagation of Selection into Logic Programs
by: Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan v. 41 i. 2 p. 157 - 180
Procedural Languages for Database Queries and Updates
by: Serge Abiteboul, Victor Vianu v. 41 i. 2 p. 181 - 229
Practical Arbitrary Lookahead LR Parsing
by: Manuel E. Bermudez, Karl M. Schimpf v. 41 i. 2 p. 230 - 250
On the Complexity of Ranking
by: Lane A. Hemachandra, Steven Rudich v. 41 i. 2 p. 251 - 271
On Uniformity within NC¹
by: David A. Mix Barrington, Neil Immerman, Howard Straubing v. 41 i. 3 p. 274 - 306
Pseudorandom Sources for BPP
by: Jack H. Lutz v. 41 i. 3 p. 307 - 320
On the Theory of the PTIME Degrees of the Recursive Sets
by: Juichi Shinoda, Theodore A. Slaman v. 41 i. 3 p. 321 - 366
Self-Reducibility
by: José L. Balcázar v. 41 i. 3 p. 367 - 388
Cook Reducibility is Faster than Karp Reduciblity in NP
by: Luc Longpré, Paul Young v. 41 i. 3 p. 389 - 401
Relations between Communication Complexity Classes
by: Bernd Halstenberg, Rüdiger Reischuk v. 41 i. 3 p. 402 - 429
Prediction-Preserving Reducibility
by: Leonard Pitt, Manfred K. Warmuth v. 41 i. 3 p. 430 - 467

1989

A Provably Efficient Algorithm for Dynamic Storage Allocation
by: Edward G. Coffman Jr., Frank Thomson Leighton v. 38 i. 1 p. 2 - 35
Embedding Planar Graphs in Four Pages
by: Mihalis Yannakakis v. 38 i. 1 p. 36 - 67
With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy
by: Jin-yi Cai v. 38 i. 1 p. 68 - 85
Making Data Structures Persistent
by: James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan v. 38 i. 1 p. 86 - 124
Optimal Parallel Selection has Complexity O(Log Log n)
by: Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi v. 38 i. 1 p. 125 - 133
On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines
by: Zvi Galil, Ravi Kannan, Endre Szemerédi v. 38 i. 1 p. 134 - 149
Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹
by: David A. Mix Barrington v. 38 i. 1 p. 150 - 164
Topologically Sweeping an Arrangement
by: Herbert Edelsbrunner, Leonidas J. Guibas v. 38 i. 1 p. 165 - 194
The Complexity of Reasoning about Knowledge and Time. I. Lower Bounds
by: Joseph Y. Halpern, Moshe Y. Vardi v. 38 i. 1 p. 195 - 237
Automatic Generation of Test Data for Relational Queries
by: Heikki Mannila, Kari-Jouko Räihä v. 38 i. 2 p. 240 - 258
Data Independent Recursion in Deductive Databases
by: Jeffrey F. Naughton v. 38 i. 2 p. 259 - 289
Minimalism, Justification and Non-Monotonicity in Deductive Databases
by: Nicole Bidoit, Richard Hull v. 38 i. 2 p. 290 - 325
A Calculus for Complex Objects
by: François Bancilhon, Setrag Khoshafian v. 38 i. 2 p. 326 - 340
On the Convergence of Query Evaluation
by: Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman v. 38 i. 2 p. 341 - 359
Deleting Completed Transactions
by: Thanasis Hadzilacos, Mihalis Yannakakis v. 38 i. 2 p. 360 - 379
A Characterization of Finite fd-Acyclicity
by: Yehoshua Sagiv, Oded Shmueli v. 38 i. 2 p. 380 - 404
Rearranging Data to Maximize the Efficiency of Compression
by: Frank Olken, Doron Rotem v. 38 i. 2 p. 405 - 430
Lower Bounds for Language Recognition on Two-Dimensional Alternating Multihead Machines
by: Juraj Hromkovic, Katsushi Inoue, Itsuo Takanami v. 38 i. 3 p. 431 - 451
On Iterative and Cellular Tree Arrays
by: Oscar H. Ibarra, Tao Jiang, Jik H. Chang v. 38 i. 3 p. 452 - 473
Serialization of Concurrent Programs
by: Marie-Paule Flé v. 38 i. 3 p. 474 - 493
Fast and Efficient Solution of Path Algebra Problems
by: Victor Y. Pan, John H. Reif v. 38 i. 3 p. 494 - 510
Positive Relativizations of the P = ? NP Problem
by: Craig A. Rich v. 38 i. 3 p. 511 - 523
Strong Nondeterministic Turing Reduction - A Technique for Proving Intractability
by: Moon-Jung Chung, Bala Ravikumar v. 39 i. 1 p. 2 - 20
On Hiding Information from an Oracle
by: Martín Abadi, Joan Feigenbaum, Joe Kilian v. 39 i. 1 p. 21 - 50
Descriptive Characterizations of Computational Complexity
by: Daniel Leivant v. 39 i. 1 p. 51 - 83
Probabilistic Complexity Classes and Lowness
by: Uwe Schöning v. 39 i. 1 p. 84 - 100
Some Consequences of the Existence of Pseudorandom Generators
by: Eric Allender v. 39 i. 1 p. 101 - 124
Optimal Shortest Path Queries in a Simple Polygon
by: Leonidas J. Guibas, John Hershberger v. 39 i. 2 p. 126 - 152
Parallel Construction of Subdivision Hierarchies
by: N. Dadoun, David G. Kirkpatrick v. 39 i. 2 p. 153 - 165
Orthogonally Convex Coverings of Orthogonal Polygons without Holes
by: Joseph C. Culberson, Robert A. Reckhow v. 39 i. 2 p. 166 - 204
There are Planar Graphs Almost as Good as the Complete Graph
by: Paul Chew v. 39 i. 2 p. 205 - 219
Computing Geodesic Furthest Neighbors in Simple Polygons
by: Subhash Suri v. 39 i. 2 p. 220 - 235
On Finite-Precision Representations of Geometric Objects
by: Kokichi Sugihara v. 39 i. 2 p. 236 - 247
Honest Polynomial Time Reducibilities and the P = ? NP Problem
by: Klaus Ambos-Spies v. 39 i. 3 p. 250 - 281
P^(NP[O(log n)]) and Sparse Turing-Complete Sets for NP
by: Jim Kadin v. 39 i. 3 p. 282 - 298
The Strong Exponential Hierarchy Collapses
by: Lane A. Hemachandra v. 39 i. 3 p. 299 - 322
Ordered Vertex Removal and Subgraph Problems
by: Raymond Greenlaw v. 39 i. 3 p. 323 - 342
Solving Reflexive Domain Equations in a Category of Complete Metric Spaces
by: Pierre America, Jan J. M. M. Rutten v. 39 i. 3 p. 343 - 375
The Set Coincidence Game: Complexity, Attainability, and Symmetric Strategies
by: A. G. Robinson, A. J. Goldman v. 39 i. 3 p. 376 - 387

1988

Group Actions and Learning for a Family of Automata
by: Pierre Baldi v. 36 i. 1 p. 1 - 15
On Alternating omega-Automata
by: Peter A. Lindsay v. 36 i. 1 p. 16 - 24
Automorphism Groups and Factor Automata of Strongly Connected Automata
by: Masashi Katsura v. 36 i. 1 p. 25 - 65
Independence of the Equational Axioms for Iteration Theories
by: Zoltán Ésik v. 36 i. 1 p. 66 - 76
Multilevel Nested Relational Structures
by: Dirk Van Gucht, Patrick C. Fischer v. 36 i. 1 p. 77 - 105
White Pebbles Help
by: Robert E. Wilber v. 36 i. 2 p. 108 - 124
A Simple Three-Dimensional Real-Time Reliable Cellular Array
by: Péter Gács, John H. Reif v. 36 i. 2 p. 125 - 147
Self-organizing Sequential Search and Hilbert's Inequalities
by: Fan R. K. Chung, D. J. Hajela, Paul D. Seymour v. 36 i. 2 p. 148 - 157
Transition Systems, Metric Spaces and Ready Sets in the Semantics of Uniform Concurrency
by: J. W. de Bakker, John-Jules Ch. Meyer, Ernst-Rüdiger Olderog, Jeffery I. Zucker v. 36 i. 2 p. 158 - 224
The Complexity of Parallel Search
by: Richard M. Karp, Eli Upfal, Avi Wigderson v. 36 i. 2 p. 225 - 253
Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes
by: László Babai, Shlomo Moran v. 36 i. 2 p. 254 - 276
Parallel Computation with Threshold Functions
by: Ian Parberry, Georg Schnitger v. 36 i. 3 p. 278 - 302
A Measure of Relativized Space Which Is Faithful With Respect to Depth
by: Christopher B. Wilson v. 36 i. 3 p. 303 - 312
Lower Bound Arguments with "Inaccessible" Numbers
by: Martin Dietzfelbinger, Wolfgang Maass v. 36 i. 3 p. 313 - 335
Isomorphisms and 1-L Reductions
by: Eric Allender v. 36 i. 3 p. 336 - 350
Relativized Alternation and Space-Bounded Computation
by: Jonathan F. Buss v. 36 i. 3 p. 351 - 378
Expanders, Randomness, or Time versus Space
by: Michael Sipser v. 36 i. 3 p. 379 - 383
The Topology of Provability in Complexity Theory
by: Kenneth W. Regan v. 36 i. 3 p. 384 - 432
Probabilistic Quantifiers and Games
by: Stathis Zachos v. 36 i. 3 p. 433 - 451
Probabilistic Game Automata
by: Anne Condon, Richard E. Ladner v. 36 i. 3 p. 452 - 489
The Complexity of Optimization Problems
by: Mark W. Krentel v. 36 i. 3 p. 490 - 509
The Complexity of Facets Resolved
by: Christos H. Papadimitriou, David Wolfe v. 37 i. 1 p. 2 - 13
The Complexity of Recognizing Polyhedral Scenes
by: Lefteris M. Kirousis, Christos H. Papadimitriou v. 37 i. 1 p. 14 - 38
Parallel Algorithms for Solvable Permutation Groups
by: Eugene M. Luks, Pierre McKenzie v. 37 i. 1 p. 39 - 62
Fast String Matching with k Differences
by: Gad M. Landau, Uzi Vishkin v. 37 i. 1 p. 63 - 78
How Easy is Local Search?
by: David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis v. 37 i. 1 p. 79 - 100
Simulating Two Pushdown Stores by One Tape in O(n^1.5 sqrt(log n)) Time
by: Ming Li v. 37 i. 1 p. 101 - 116
Meanders and Their Applications in Lower Bounds Arguments
by: Noga Alon, Wolfgang Maass v. 37 i. 2 p. 118 - 129
Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs
by: Prabhakar Raghavan v. 37 i. 2 p. 130 - 143
k+1 Heads Are Better than k for PDAs
by: Marek Chrobak, Ming Li v. 37 i. 2 p. 144 - 155
Minimum Disclosure Proofs of Knowledge
by: Gilles Brassard, David Chaum, Claude Crépeau v. 37 i. 2 p. 156 - 189
An Efficient Parallel Algorithm for Planarity
by: Philip N. Klein, John H. Reif v. 37 i. 2 p. 190 - 246
Collapsing Degrees
by: Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer v. 37 i. 2 p. 247 - 268
Pushdown Automata with Reversal-Bounded Counters
by: Tat-hung Chan v. 37 i. 3 p. 269 - 291
On Locating Minimum Feedback Vertex Sets
by: Errol L. Lloyd, Mary Lou Soffa v. 37 i. 3 p. 292 - 311
Graph Isomorphism is in the Low Hierarchy
by: Uwe Schöning v. 37 i. 3 p. 312 - 323
An Unpredictability Approach to Finite-State Randomness
by: Mary G. O'Connor v. 37 i. 3 p. 324 - 336
Distributed Algorithms for Selection in Sets
by: Greg N. Frederickson v. 37 i. 3 p. 337 - 348
Completeness Results for Conflict-Free Vector Replacement Systems
by: Rodney R. Howell, Louis E. Rosier v. 37 i. 3 p. 349 - 366
Deterministic Tree Pushdown Automata and Monadic Tree Rewriting Systems
by: Kai Salomaa v. 37 i. 3 p. 367 - 394
Correction to "Computational Complexity of Algebraic Functions"
by: Nicholas Pippenger v. 37 i. 3 p. 395 - 399

1987

On Observational Equivalence and Algebraic Specification
by: Donald Sannella, Andrzej Tarlecki v. 34 i. 2/3 p. 150 - 178
Parameter-Preserving Data Type Specifications
by: Peter Padawitz v. 34 i. 2/3 p. 179 - 209
Bisimulations and Abstraction Homomorphisms
by: Ilaria Castellani v. 34 i. 2/3 p. 210 - 235
Specification and Top-Down Design of Distributed Systems
by: Manfred Broy v. 34 i. 2/3 p. 236 - 265
Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples
by: Johann A. Makowsky v. 34 i. 2/3 p. 266 - 292
Algebraic Specification of Modules and Their Basic Interconnections
by: Edward K. Blum, Hartmut Ehrig, Francesco Parisi-Presicce v. 34 i. 2/3 p. 293 - 339
On the Implementation of Abstract Data Types by Programming Language Constructs
by: Axel Poigné, Josef Voss v. 34 i. 2/3 p. 340 - 376
Amalgamation of Graph Transformations: A Synchronization Mechanism
by: Paul Boehm, Harald-Reto Fonio, Annegret Habel v. 34 i. 2/3 p. 377 - 408
Inductively Defined Functions in Functional Programming Languages
by: Rod M. Burstall v. 34 i. 2/3 p. 409 - 421
Concurrent Histories: A Basis for Observing Distributed Systems
by: Pierpaolo Degano, Ugo Montanari v. 34 i. 2/3 p. 422 - 461
Decision Procedures for Elementary Sublanguages of Set Theory. V. Multilevel Syllogistic Extended by the General Union Operator
by: Domenico Cantone, Alfredo Ferro, Jacob T. Schwartz v. 34 i. 1 p. 1 - 18
Upper Bounds for Time-Space Trade-Offs in Sorting and Selection
by: Greg N. Frederickson v. 34 i. 1 p. 19 - 26
Expressive Completeness Failure in Branching Time Structures
by: Amihood Amir v. 34 i. 1 p. 27 - 42
Expressive Completeness Failure in Branching Time Structures
by: Amihood Amir v. 34 i. 1 p. 27 - 42
River Routing in VLSI
by: Andranik Mirzaian v. 34 i. 1 p. 43 - 54
An Analysis of the Nonemptiness Problem for Classes of Reversal-Bounded Multicounter Machines
by: Rodney R. Howell, Louis E. Rosier v. 34 i. 1 p. 55 - 74
A Note on the Two-Variable Pattern-Finding Problem
by: Ker-I Ko, Chin-Ming Hua v. 34 i. 1 p. 75 - 86
Basic Tree Transducers
by: Heiko Vogler v. 34 i. 1 p. 87 - 128
Succinct Representation of Regular Sets Using Gotos and Boolean Variables
by: Karl R. Abrahamson v. 34 i. 1 p. 129 - 148
Design of Relational Database Schemes by Deleting Attributes in the Canonical Decomposition
by: Joachim Biskup, Renate Meyer v. 35 i. 1 p. 1 - 22
Communication in Concurrent Dynamic Logic
by: David Peleg v. 35 i. 1 p. 23 - 58
Complementing Deterministic Büchi Automata in Polynomial Time
by: Robert P. Kurshan v. 35 i. 1 p. 59 - 71
Union and Actualization of Module Specifications: Some Compatibility Results
by: Francesco Parisi-Presicce v. 35 i. 1 p. 72 - 95
Edge-Connectivity Augmentation Problems
by: Toshimasa Watanabe, Akira Nakamura v. 35 i. 1 p. 96 - 144
Sigma_2 SPACE(n) is Closed under Complement
by: Seinosuke Toda v. 35 i. 2 p. 145 - 152
A Lower Bound for Read-Once-Only Branching Programs
by: László Babai, Péter Hajnal, Endre Szemerédi, György Turán v. 35 i. 2 p. 153 - 162
On Flowchart Theories. I. The Deterministic Case
by: Gheorghe Stefanescu v. 35 i. 2 p. 163 - 191
Handle NLC Grammars and R.E. Languages
by: Michael G. Main, Grzegorz Rozenberg v. 35 i. 2 p. 192 - 205
An Algebra of Processes
by: Józef Winkowski, Andrea Maggiolo-Schettini v. 35 i. 2 p. 206 - 228
Dynamic Algebras with Test
by: Vera Trnková, Jan Reiterman v. 35 i. 2 p. 229 - 242
Groups and NTS Languages
by: Jean-Michel Autebert, Luc Boasson, Géraud Sénizergues v. 35 i. 2 p. 243 - 267
Refined Complexity Analysis for Heap Operations
by: Michael L. Fredman, Thomas H. Spencer v. 35 i. 3 p. 269 - 284
On Deciding the Confluence of a Finite String-Rewriting System on a Given Congruence Class
by: Friedrich Otto v. 35 i. 3 p. 285 - 310
On Commutative Context-Free Languages
by: Joffroy Beauquier, Meera Blattner, Michel Latteux v. 35 i. 3 p. 311 - 320
The Verso Algebra or How to Answer Queries with Fewer Joins
by: Nicole Bidoit v. 35 i. 3 p. 321 - 364
Algebraic Solutions to Recursion Schemes
by: David B. Benson, Irène Guessarian v. 35 i. 3 p. 365 - 400

1986

Binary Trees and Uniform Distribution of Traffic Cutback
by: Shuo-Yen Robert Li v. 32 i. 1 p. 1 - 14
Reliable Computation with Cellular Automata
by: Péter Gács v. 32 i. 1 p. 15 - 78
About the Paterson-Wegman Linear Unification Algorithm
by: Dennis de Champeaux v. 32 i. 1 p. 79 - 90
Time-Space Trade-offs for Branching Programs
by: Ingo Wegener v. 32 i. 1 p. 91 - 96
"During" Cannot be Expressed by "After"
by: Pawel Urzyczyn v. 32 i. 1 p. 97 - 104
A Multiparameter Analysis of the Boundedness Problem for Vector Addition Systems
by: Louis E. Rosier, Hsu-Chun Yen v. 32 i. 1 p. 105 - 135
New Algorithms for Multilink Robot Arms
by: Vitit Kantabutra, S. Rao Kosaraju v. 32 i. 1 p. 136 - 153
Reporting and Counting Segment Intersections
by: Bernard Chazelle v. 32 i. 2 p. 156 - 182
Automata-Theoretic Techniques for Modal Logics of Programs
by: Moshe Y. Vardi, Pierre Wolper v. 32 i. 2 p. 183 - 221
Threshold Functions and Bounded Depth Monotone Circuits
by: Ravi B. Boppana v. 32 i. 2 p. 222 - 229
On the Possibility and Impossibility of Achieving Clock Synchronization
by: Danny Dolev, Joseph Y. Halpern, H. Raymond Strong v. 32 i. 2 p. 230 - 250
The Complexity of Elementary Algebra and Geometry
by: Michael Ben-Or, Dexter Kozen, John H. Reif v. 32 i. 2 p. 251 - 264
Finding Small Simple Cycle Separators for 2-Connected Planar Graphs
by: Gary L. Miller v. 32 i. 3 p. 265 - 279
Efficient Symbolic Analysis of Programs
by: John H. Reif, Harry R. Lewis v. 32 i. 3 p. 280 - 314
A Simple Undecidable Problem: Existential Agreement of Inverses of Two Morphisms on a Regular Language
by: Juhani Karhumäki, Yael Maon v. 32 i. 3 p. 315 - 322
Conditional Rewrite Rules: Confluence and Termination
by: Jan A. Bergstra, Jan Willem Klop v. 32 i. 3 p. 323 - 362
Uniform Normal Form for General Time-Bounded Complexity Classes
by: Bernard R. Hodgson, Clement F. Kent v. 32 i. 3 p. 363 - 369
Effective Choice Functions and Index Sets
by: James C. Owings v. 32 i. 3 p. 370 - 373
Domino-Tiling Games
by: Bogdan S. Chlebus v. 32 i. 3 p. 374 - 392
First-Order Logic and Star-Free Sets
by: Dominique Perrin, Jean-Eric Pin v. 32 i. 3 p. 393 - 406
"Global" Graph Problems Tend to Be Intractable
by: N. Lakshmipathy, Karl Winklmann v. 32 i. 3 p. 407 - 428
Fully Abstract Submodels of Typed Lambda Calculi
by: Ketan Mulmuley v. 33 i. 1 p. 2 - 46
Polymorphic Arrays: A Novel VLSI Layout for Systolic Computers
by: Amos Fiat, Adi Shamir v. 33 i. 1 p. 47 - 65
An Implicit Data Structure Supporting Insertion, Deletion, and Search in O(log² n) Time
by: J. Ian Munro v. 33 i. 1 p. 66 - 74
Generating Quasi-random Sequences from Semi-random Sources
by: Miklos Santha, Umesh V. Vazirani v. 33 i. 1 p. 75 - 87
A Lower Bound for Probabilistic Algorithms for Finite State Machines
by: Albert G. Greenberg, Alan Weiss v. 33 i. 1 p. 88 - 105
Probabilistic Communication Complexity
by: Ramamohan Paturi, Janos Simon v. 33 i. 1 p. 106 - 123
Design by Example: An Application of Armstrong Relations
by: Heikki Mannila, Kari-Jouko Räihä v. 33 i. 2 p. 126 - 141
Querying Logical Databases
by: Moshe Y. Vardi v. 33 i. 2 p. 142 - 160
Deadlock-Freedom (and Safety) of Transactions in a Distributed Database
by: Ouri Wolfson, Mihalis Yannakakis v. 33 i. 2 p. 161 - 178
Chordality Properties on Graphs and Minimal Conceptual Connections in Semantic Data Models
by: Giorgio Ausiello, Alessandro D'Atri, Marina Moscarini v. 33 i. 2 p. 179 - 202
Partition Semantics for Relations
by: Stavros S. Cosmadakis, Paris C. Kanellakis, Nicolas Spyratos v. 33 i. 2 p. 203 - 233
Equivalence of Views by Query Capacity
by: Tim Connors v. 33 i. 2 p. 234 - 274
Concurrent Operations on B*-Trees with Overtaking
by: Yehoshua Sagiv v. 33 i. 2 p. 275 - 296
Algorithmic Aspects of Multiversion Concurrency Control
by: Thanasis Hadzilacos, Christos H. Papadimitriou v. 33 i. 2 p. 297 - 310
A Complete Rule for Equifair Termination
by: Orna Grumberg, Nissim Francez, Shmuel Katz v. 33 i. 3 p. 313 - 332
Quasi-varieties in Abstract Algebraic Institutions
by: Andrzej Tarlecki v. 33 i. 3 p. 333 - 360
Non First Normal Form Relations: An Algebra Allowing Data Restructuring
by: Serge Abiteboul, Nicole Bidoit v. 33 i. 3 p. 361 - 393
A Theory of Orbital Behavior in a Class of Nonlinear Systems: Chaos and a Signature-Based Approach
by: Martin E. Kaliski, S. Yunkap Kwankam, Pamela Halpern, David Shulman v. 33 i. 3 p. 394 - 414
The Bounded Degree Problem for NLC Grammars is Decidable
by: Dirk Janssens, Grzegorz Rozenberg, Emo Welzl v. 33 i. 3 p. 415 - 422
A Representation Theorem of Infinite Dimensional Algebras and Applications to Language Theory
by: Günter Hotz v. 33 i. 3 p. 423 - 455
Membership for Growing Context-Sensitive Grammars is Polynomial
by: Elias Dahlhaus, Manfred K. Warmuth v. 33 i. 3 p. 456 - 472
Analysis of Bounded Linear Cellular Automata Based on a Method of Image Charges
by: Howard C. Card, Adonios Thanailakis, Werner Pries, Robert D. McLeod v. 33 i. 3 p. 473 - 480

1985

Decision Procedures and Expressiveness in the Temporal Logic of Branching Time
by: E. Allen Emerson, Joseph Y. Halpern v. 30 i. 1 p. 1 - 24
Tree Pushdown Automata
by: Karl M. Schimpf, Jean H. Gallier v. 30 i. 1 p. 25 - 40
A Multiprocess Network Logic with Temporal and Spatial Modalities
by: John H. Reif, A. Prasad Sistla v. 30 i. 1 p. 41 - 53
A Linear Algorithm for Embedding Planar Graphs Using PQ-Trees
by: Norishige Chiba, Takao Nishizeki, Shigenobu Abe, Takao Ozawa v. 30 i. 1 p. 54 - 76
Variations on the Technique of Duris and Galil
by: Marek Chrobak v. 30 i. 1 p. 77 - 85
Hierarchies of Hyper-AFLs
by: Joost Engelfriet v. 30 i. 1 p. 86 - 115
Solitaire Automata
by: Richard E. Ladner, Jeffrey K. Norman v. 30 i. 1 p. 116 - 129
Routing, Merging, and Sorting on Parallel Models of Computation
by: Allan Borodin, John E. Hopcroft v. 30 i. 1 p. 130 - 145
Speedups of Deterministic Machines by Synchronous Parallel Machines
by: Patrick W. Dymond, Martin Tompa v. 30 i. 2 p. 149 - 161
A Probabilistic PDL
by: Dexter Kozen v. 30 i. 2 p. 162 - 178
Solvability by Radicals is in Polynomial Time
by: Susan Landau, Gary L. Miller v. 30 i. 2 p. 179 - 208
A Linear-Time Algorithm for a Special Case of Disjoint Set Union
by: Harold N. Gabow, Robert Endre Tarjan v. 30 i. 2 p. 209 - 221
Unbounded Fan-In Circuits and Associative Functions
by: Ashok K. Chandra, Steven Fortune, Richard J. Lipton v. 30 i. 2 p. 222 - 234
Factoring Multivariate Polynomials over Finite Fields
by: Arjen K. Lenstra v. 30 i. 2 p. 235 - 248
Pattern Selector Grammars and Several Parsing Algorithms in the Context-Free Style
by: Jakob Gonczarowski, Eliahu Shamir v. 30 i. 3 p. 249 - 273
Cost Functors and Optimal Realization
by: Antonio Bahamonde v. 30 i. 3 p. 274 - 290
Dynamical Characteristics of Linear Cellular Automata
by: Hirotomo Aso, Namio Honda v. 30 i. 3 p. 291 - 317
Free Semiring-Representations and Nondeterminism
by: Michael G. Main, David B. Benson v. 30 i. 3 p. 318 - 328
Area-Period Tradeoffs for Multiplication of Rectangular Matrices
by: Ferng-Ching Lin, I-Chen Wu v. 30 i. 3 p. 329 - 342
Complexity of Certain Decision Problems about Congruential Languages
by: Paliath Narendran, Colm Ó'Dúnlaing, Heinrich Rolletschek v. 30 i. 3 p. 343 - 358
Sylow's Theorem in Polynomial Time
by: William M. Kantor v. 30 i. 3 p. 359 - 394
Qualitative Relativizations of Complexity Classes
by: Ronald V. Book, Timothy J. Long, Alan L. Selman v. 30 i. 3 p. 395 - 413
Formal Analysis of a Systolic System for Finite Element Stiffness Matrices
by: Rami G. Melhem v. 31 i. 1 p. 1 - 27
On the Power of Alternation in Automata Theory
by: Juraj Hromkovic v. 31 i. 1 p. 28 - 39
Behavior of a Class of Nonlinear Discrete-Time Systems
by: Martin E. Kaliski, Quentin L. Klein v. 31 i. 1 p. 40 - 62
A Matching Problem in the Plane
by: Mikhail J. Atallah v. 31 i. 1 p. 63 - 70
Macro Tree Transducers
by: Joost Engelfriet, Heiko Vogler v. 31 i. 1 p. 71 - 146
Scaling Algorithms for Network Problems
by: Harold N. Gabow v. 31 i. 2 p. 148 - 168
Relativized Circuit Complexity
by: Christopher B. Wilson v. 31 i. 2 p. 169 - 181
Probabilistic Counting Algorithms for Data Base Applications
by: Philippe Flajolet, G. Nigel Martin v. 31 i. 2 p. 182 - 209
Improved Upper Bounds on Shellsort
by: Janet Incerpi, Robert Sedgewick v. 31 i. 2 p. 210 - 224
Irreducibility of Multivariate Polynomials
by: Joachim von zur Gathen v. 31 i. 2 p. 225 - 264
Factoring Sparse Multivariate Polynomials
by: Joachim von zur Gathen, Erich Kaltofen v. 31 i. 2 p. 265 - 287
Games Against Nature
by: Christos H. Papadimitriou v. 31 i. 2 p. 288 - 301
The Equivalence and Inclusion Problems for NTS Languages
by: Géraud Sénizergues v. 31 i. 3 p. 303 - 331
NTS Languages Are Deterministic and Congruential
by: Luc Boasson, Géraud Sénizergues v. 31 i. 3 p. 332 - 342
Interactions between Dependencies and Nested Relational Structures
by: Patrick C. Fischer, Lawrence V. Saxton, Stan J. Thomas, Dirk Van Gucht v. 31 i. 3 p. 343 - 354
Serializability Theory for Replicated Databases
by: Philip A. Bernstein, Nathan Goodman v. 31 i. 3 p. 355 - 374
Axiomatizing Schemes and Their Behaviors
by: Stephen L. Bloom, Zoltán Ésik v. 31 i. 3 p. 375 - 393
Structural Properties of the String Statistics Problem
by: Alberto Apostolico, Franco P. Preparata v. 31 i. 3 p. 394 - 411

1984

The Implication and Finite Implication Problems for Typed Template Dependencies
by: Moshe Y. Vardi v. 28 i. 1 p. 3 - 28
Inclusion Dependencies and Their Interaction with Functional Dependencies
by: Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou v. 28 i. 1 p. 29 - 59
The Tree Projection Theorem and Relational Query Processing
by: Nathan Goodman, Oded Shmueli v. 28 i. 1 p. 60 - 79
The Relational Model of Data and Cylindric Algebras
by: Tomasz Imielinski, Witold Lipski Jr. v. 28 i. 1 p. 80 - 102
Is Distributed Locking Harder?
by: Paris C. Kanellakis, Christos H. Papadimitriou v. 28 i. 1 p. 103 - 120
Independent Database Schemas
by: Marc H. Graham, Mihalis Yannakakis v. 28 i. 1 p. 121 - 141
Database Relations with Null Values
by: Carlo Zaniolo v. 28 i. 1 p. 142 - 166
Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies
by: David S. Johnson, Anthony C. Klug v. 28 i. 1 p. 167 - 189
A Probabilistic Dynamic Logic
by: Yishai A. Feldman, David Harel v. 28 i. 2 p. 193 - 215
Space-Bounded Hierarchies and Probabilistic Computations
by: Walter L. Ruzzo, Janos Simon, Martin Tompa v. 28 i. 2 p. 216 - 230
Data Structures for Distributed Counting
by: Martin Fürer v. 28 i. 2 p. 231 - 243
The Complexity of Facets (and Some Facets of Complexity)
by: Christos H. Papadimitriou, Mihalis Yannakakis v. 28 i. 2 p. 244 - 259
Communication Complexity
by: Christos H. Papadimitriou, Michael Sipser v. 28 i. 2 p. 260 - 269
Probabilistic Encryption
by: Shafi Goldwasser, Silvio Micali v. 28 i. 2 p. 270 - 299
A Framework for Solving VLSI Graph Layout Problems
by: Sandeep N. Bhatt, Frank Thomson Leighton v. 28 i. 2 p. 300 - 343
On the Complexity of Iterated Shuffle
by: Manfred K. Warmuth, David Haussler v. 28 i. 3 p. 345 - 358
Minimizing Access Pointers into Trees and Arrays
by: Michael C. Loui v. 28 i. 3 p. 359 - 378
New Trie Data Structures Which Support Very Fast Search Operations
by: Dan E. Willard v. 28 i. 3 p. 379 - 394
The Complexity of Monadic Recursion Schemes: Exponential Time Bounds
by: Harry B. Hunt III, Daniel J. Rosenkrantz v. 28 i. 3 p. 395 - 419
One-Layer Routing without Component Constraints
by: Errol L. Lloyd, S. S. Ravi v. 28 i. 3 p. 420 - 438
A Complete Inference System for a Class of Regular Behaviours
by: Robin Milner v. 28 i. 3 p. 439 - 466
Exponential Bounds for the Running Time of a Selection Algorithm
by: Luc Devroye v. 29 i. 1 p. 1 - 7
Complete Problems in the First-Order Predicate Calculus
by: David A. Plaisted v. 29 i. 1 p. 8 - 35
An n log n Algorithm for Determining the Congruity of Polyhedra
by: Kokichi Sugihara v. 29 i. 1 p. 36 - 47
Finding Pseudoperipheral Nodes in Graphs
by: Jan K. Pachl v. 29 i. 1 p. 48 - 53
Commutative One-Counter Languages are Regular
by: Michel Latteux, Grzegorz Rozenberg v. 29 i. 1 p. 54 - 57
On the Fixpoints of Nondeterministic Recursive Definitions
by: Tsong Yueh Chen v. 29 i. 1 p. 58 - 79
A Generalized Nexttime Operator in Temporal Logic
by: Fred Kröger v. 29 i. 1 p. 80 - 98
Weak Equivalence in a Class of Structured Program Schemes
by: Douglas R. Troeger v. 29 i. 1 p. 99 - 117
Consistency in Nondeterministic Storage
by: Walter J. Savitch, Patrick W. Dymond v. 29 i. 1 p. 118 - 132
New Algorithms for the LCS Problem
by: W. J. Hsu, M. W. Du v. 29 i. 2 p. 133 - 152
On Cancellation Properties of Languages which are Supports of Ration Power Series
by: Antonio Restivo, Christophe Reutenauer v. 29 i. 2 p. 153 - 159
Equivalences among Logics of Programs
by: Albert R. Meyer, Jerzy Tiuryn v. 29 i. 2 p. 160 - 170
Indecomposable Maps in Tessellation Structures of Arbitrary Dimension
by: Hiromi Miyajima, Masateru Harao, Shoichi Noguchi v. 29 i. 2 p. 171 - 182
Time-Space Tradeoffs for Matrix Multiplication and the Discrete Fourier Transform on any General Sequential Random-Access Computer
by: Yaacov Yesha v. 29 i. 2 p. 183 - 197
Towards a Hierarchy of Nets
by: Sara Porat, Michael Yoeli v. 29 i. 2 p. 198 - 206
Multi-version Concurrency Control Scheme for a Database System
by: Shojiro Muro, Tiko Kameda, Toshimi Minoura v. 29 i. 2 p. 207 - 224
On the Computational Complexity of Path Cover Problems
by: Simeon C. Ntafos, Teofilo F. Gonzalez v. 29 i. 2 p. 225 - 242
The Performance of Multilective VLSI Algorithms
by: John E. Savage v. 29 i. 2 p. 243 - 273
The Complexity of Two-Player Games of Incomplete Information
by: John H. Reif v. 29 i. 2 p. 274 - 301
On Two-Tape Real-Time Computation and Queues
by: Paul M. B. Vitányi v. 29 i. 3 p. 303 - 311
An Application of Cohen's Result on Star Height to the Theory of Control Structures
by: Tatsuya Motoki v. 29 i. 3 p. 312 - 329
Finding Euler Tours in Parallel
by: Mikhail J. Atallah, Uzi Vishkin v. 29 i. 3 p. 330 - 337
GYO Reductions, Canonical Connections, Tree and Cyclic Schemas, and Tree Projections
by: Nathan Goodman, Oded Shmueli, Yong Chiang Tay v. 29 i. 3 p. 338 - 358
Undecidability of PDL with L={a^(2i)|i&gt=0}
by: David Harel, Mike Paterson v. 29 i. 3 p. 359 - 365
Extended Macro Grammars and Stack Controlled Machines
by: Joost Engelfriet, Giora Slutzki v. 29 i. 3 p. 366 - 408
Optimization of Distributed Tree Queries
by: Clement T. Yu, Z. Meral Özsoyoglu, K. Lam v. 29 i. 3 p. 409 - 445

1983

Effects of Updates on Optimality in Tries
by: Douglas Comer v. 26 i. 1 p. 1 - 13
Langages à un Compteur
by: Michel Latteux v. 26 i. 1 p. 14 - 33
Context Free Normal Systems and ETOL Systems
by: Andrzej Ehrenfeucht, Joost Engelfriet, Grzegorz Rozenberg v. 26 i. 1 p. 34 - 46
On the Zero-Inequivalence Problem for Loop Programs
by: Oscar H. Ibarra, Brian S. Leininger v. 26 i. 1 p. 47 - 64
Size-Space Tradeoffs for Oblivious Computations
by: David A. Carlson, John E. Savage v. 26 i. 1 p. 65 - 81
Checking Sets, Test Sets, Rich Languages and Commutatively Closed Languages
by: Jürgen Albert, Derick Wood v. 26 i. 1 p. 82 - 91
Multiplicative Complexity and Algebraic Structure
by: Dave Riffelmacher v. 26 i. 1 p. 92 - 106
On the Transformation Semigroups of Finite Automata
by: Toshimasa Watanabe, Akira Nakamura v. 26 i. 1 p. 107 - 138
Network Structure and the Firing Squad Synchronization Problem
by: John J. Grefenstette v. 26 i. 1 p. 139 - 152
Lower Bounds on the Size of Deterministic Parsers
by: Esko Ukkonen v. 26 i. 2 p. 153 - 170
On the Equality of Grammatical Families
by: Seymour Ginsburg, Jonathan Goldstine, Edwin H. Spanier v. 26 i. 2 p. 171 - 196
Edge-Contraction Problems
by: Takao Asano, Tomio Hirata v. 26 i. 2 p. 197 - 208
On Self-Reducibility and Weak P-Selectivity
by: Ker-I Ko v. 26 i. 2 p. 209 - 221
Propositional Dynamic Logic of Nonregular Programs
by: David Harel, Amir Pnueli, Jonathan Stavi v. 26 i. 2 p. 222 - 243
On the Complexity of LL(k) Testing
by: Seppo Sippu, Eljas Soisalon-Soininen v. 26 i. 2 p. 244 - 268
Computation of Boolean Functions on Networks of Binary Automata
by: Maurice Tchuente v. 26 i. 2 p. 269 - 277
Time-Space-Optimal String Matching
by: Zvi Galil, Joel I. Seiferas v. 26 i. 3 p. 280 - 294
Groups, the Theory of Ends, and Context-Free Languages
by: David E. Muller, Paul E. Schupp v. 26 i. 3 p. 295 - 310
Polynomial Time Computations in Models of ET
by: Deborah Joseph v. 26 i. 3 p. 311 - 338
An Asymptotically Optimal Layout for the Shuffle-Exchange Graph
by: Daniel J. Kleitman, Frank Thomson Leighton, Margaret Lepley, Gary L. Miller v. 26 i. 3 p. 339 - 361
A Data Structure for Dynamic Trees
by: Daniel Dominic Sleator, Robert Endre Tarjan v. 26 i. 3 p. 362 - 391
Lower Bounds for the Cycle Detection Problem
by: Faith E. Fich v. 26 i. 3 p. 392 - 409
A View of Computability on Term Algebras
by: K. N. Venkataraman, Ann Yasuhara, Frank M. Hawrusik v. 26 i. 3 p. 410 - 471
Tests for the LR-, LL-, and LC-Regular Conditions
by: Stephan Heilbrunner v. 27 i. 1 p. 1 - 13
A Low and a High Hierarchy within NP
by: Uwe Schöning v. 27 i. 1 p. 14 - 28
Port Automata and the Algebra of Concurrent Processes
by: Martha Steenstrup, Michael A. Arbib, Ernest G. Manes v. 27 i. 1 p. 29 - 50
A Method for Stepwise Refinement and Abstraction of Petri Nets
by: Ichiro Suzuki, Tadao Murata v. 27 i. 1 p. 51 - 76
On the Complexity of Chess
by: James A. Storer v. 27 i. 1 p. 77 - 100
Representation Theorems on Regular Languages
by: Kosaburo Hashiguchi v. 27 i. 1 p. 101 - 115
Remarks on Multihead Pushdown Automata and Multihead Stack Automata
by: Satoru Miyano v. 27 i. 1 p. 116 - 124
Linear Cellular Automata over Z_m
by: Masanobu Ito, Nobuyasu Osato, Masakazu Nasu v. 27 i. 1 p. 125 - 140
Recursion and Iteration in Continuous Theories: The "M-Construction"
by: Stephen L. Bloom, James W. Thatcher, Eric G. Wagner, Jesse B. Wright v. 27 i. 2 p. 148 - 164
Algebraic Characterization of Reducible Flowcharts
by: Hartmut Schmeck v. 27 i. 2 p. 165 - 199
Extensions of Iterative Congruences on Free Iterative Algebras
by: Francesco Parisi-Presicce v. 27 i. 2 p. 200 - 220
An Axiomatization of D-scheme Strong Equivalence
by: Douglas R. Troeger v. 27 i. 2 p. 221 - 224
All Solutions of a System of Recursion Equations in Infinite Trees and Other Contraction Theories
by: Stephen L. Bloom v. 27 i. 2 p. 225 - 255
Transaction Protection by Beacons
by: Michael O. Rabin v. 27 i. 2 p. 256 - 267
Correctness of Recursive Parallel Nondeterministic Flow Programs
by: Joseph A. Goguen, José Meseguer v. 27 i. 2 p. 268 - 290
Algebras of Iteration Theories
by: Zoltán Ésik v. 27 i. 2 p. 291 - 303
Implementation of Data Types by Algebraic Methods
by: Edward K. Blum, Francesco Parisi-Presicce v. 27 i. 2 p. 304 - 330
Acyclic Join Dependency and Data Base Projections
by: Richard Hull v. 27 i. 3 p. 331 - 349
A Technique for Decomposing Algorithms Which Use a Single Shared Variable
by: Nancy A. Lynch, Michael J. Fischer v. 27 i. 3 p. 350 - 377
A Normal Form for Arithmetical Representation of NP-Sets
by: Bernard R. Hodgson, Clement F. Kent v. 27 i. 3 p. 378 - 388
The Insensitivity Theorem for Nonreducing Reflexive Types
by: Egidio Astesiano, Gerardo Costa v. 27 i. 3 p. 389 - 399
Deterministic and Nondeterministic Flowchart Interpretations
by: Richard J. Lorentz, David B. Benson v. 27 i. 3 p. 400 - 433
Finite-State omega-Languages
by: Ludwig Staiger v. 27 i. 3 p. 434 - 448

1982

Computing Lower Bounds on Tensor Rank over Finite Fields
by: Sharon J. Laskowski v. 24 i. 1 p. 1 - 14
The Maximum Value Problem and NP Real Numbers
by: Ker-I Ko v. 24 i. 1 p. 15 - 35
On LLP(k) Parsers
by: Jan Pittl v. 24 i. 1 p. 36 - 68
On Some Decision Problems for RAM Programs
by: Oscar H. Ibarra, Shlomo Moran v. 24 i. 1 p. 69 - 81
Superconcentrators of Depth 2
by: Nicholas Pippenger v. 24 i. 1 p. 82 - 90
A Hierarchy of Real-Time Deterministic Languages and Their Equivalence
by: Amiram Yehudai v. 24 i. 1 p. 91 - 100
Accessibility of Values as a Determinant of Relative Complexity in Algebras
by: Nancy A. Lynch v. 24 i. 1 p. 101 - 113
Tree Constructions of Free Continuous Algebras
by: Jirí Adámek, Evelyn Nelson, Jan Reiterman v. 24 i. 1 p. 114 - 146
The Equivalence Problem for LL- and LR-Regular Grammars
by: Anton Nijholt v. 24 i. 2 p. 149 - 161
Finding the Median Distributively
by: Michael Rodeh v. 24 i. 2 p. 162 - 166
Tree Correspondence Problems
by: J. Albert, Karel Culik II v. 24 i. 2 p. 167 - 179
Quadratic Automata
by: Jerry Goldman, Steven Homer v. 24 i. 2 p. 180 - 196
The Complexity of Selection and Ranking in X+Y and Matrices with Sorted Columns
by: Greg N. Frederickson, Donald B. Johnson v. 24 i. 2 p. 197 - 208
The Computational Complexity of a Set of Quadratic Functions
by: Joseph JáJá v. 24 i. 2 p. 209 - 223
A Note on Sparse Oracles for NP
by: Timothy J. Long v. 24 i. 2 p. 224 - 232
Limitedness Theorem on Finite Automata with Distance Functions
by: Kosaburo Hashiguchi v. 24 i. 2 p. 233 - 244
Processes of Transforming Structures
by: Andrea Maggiolo-Schettini, Józef Winkowski v. 24 i. 3 p. 245 - 282
Simple Multi-Visit Attribute Grammars
by: Joost Engelfriet, Gilberto Filé v. 24 i. 3 p. 283 - 314
A Prime Decomposition Theorem for Grammatical Families
by: Seymour Ginsburg, Jonathan Goldstine, Edwin H. Spanier v. 24 i. 3 p. 315 - 361
Space Complexity in On-Line Computation
by: Hajime Machida, Takumi Kasai v. 24 i. 3 p. 362 - 372
Representation of One-One Degrees by Decision Problems for System Functions
by: Bhavani M. Thuraisingham v. 24 i. 3 p. 373 - 377
Corrigendum: Independence Results in Computer Science?
by: Deborah Joseph, Paul Young v. 24 i. 3 p. 378 - 378
Algebraic Dependencies
by: Mihalis Yannakakis, Christos H. Papadimitriou v. 25 i. 1 p. 2 - 41
Isomorphism of Graphs of Bounded Valence can be Tested in Polynomial Time
by: Eugene M. Luks v. 25 i. 1 p. 42 - 65
N-Process Mutual Exclusion with Bounded Waiting by 4 Log_2 N-Valued Shared Variable
by: Michael O. Rabin v. 25 i. 1 p. 66 - 75
Upper and Lower Bounds for First Order Expressibility
by: Neil Immerman v. 25 i. 1 p. 76 - 98
Structure and Complexity of Relational Queries
by: Ashok K. Chandra, David Harel v. 25 i. 1 p. 99 - 128
Sparse Complete Sets of NP: Solution of a Conjecture of Berman and Hartmanis
by: Stephen R. Mahaney v. 25 i. 2 p. 130 - 143
Process Logic: Expressiveness, Decidability, Completeness
by: David Harel, Dexter Kozen, Rohit Parikh v. 25 i. 2 p. 144 - 170
The Average Height of Binary Trees and Other Simple Trees
by: Philippe Flajolet, Andrew M. Odlyzko v. 25 i. 2 p. 171 - 213
A General Class of Resource Tradeoffs
by: Jon Louis Bentley, Donna J. Brown v. 25 i. 2 p. 214 - 238
Proofs by Induction in Equational Theories with Constructors
by: Gérard P. Huet, Jean-Marie Hullot v. 25 i. 2 p. 239 - 266
Expressiveness and the Completeness of Hoare's Logic
by: Jan A. Bergstra, J. V. Tucker v. 25 i. 3 p. 267 - 284
Homomorphisms between Models of Parallel Computation
by: Takumi Kasai, Raymond E. Miller v. 25 i. 3 p. 285 - 331
Subcomplete Generalizations of Graph Isomorphism
by: Christoph M. Hoffmann v. 25 i. 3 p. 332 - 359
Classifying Regular Events in Symbolic Logic
by: Wolfgang Thomas v. 25 i. 3 p. 360 - 376
An Algebraic Characterization of Some Principal Regulated Rational Cones
by: Werner Kuich v. 25 i. 3 p. 377 - 401
Deterministic Propositional Dynamic Logic: Finite Models, Complexity, and Completeness
by: Mordechai Ben-Ari, Joseph Y. Halpern, Amir Pnueli v. 25 i. 3 p. 402 - 417
The Copying Power of One-State Tree Transducers
by: Joost Engelfriet, Sven Skyum v. 25 i. 3 p. 418 - 435

1981

Some Results on Relativized Deterministic and Nondeterministic Time Hierarchies
by: Shlomo Moran v. 22 i. 1 p. 1 - 8
Regularity and Firing Sequences of Computation Graphs
by: Tsuyoshi Nakamura v. 22 i. 1 p. 9 - 28
Growth Patterns of Ordered Cellular Automata
by: Stephen J. Willson v. 22 i. 1 p. 29 - 41
The Decidability of the D0L-DT0L Equivalence Problem
by: Keijo Ruohonen v. 22 i. 1 p. 42 - 52
A Note on Structure and Looking Back Applied to the Complexity of Computable Functions
by: Paul Chew, Michael Machtey v. 22 i. 1 p. 53 - 59
On Minimal Augmentation of a Graph to Obtain an Interval Graph
by: Tatsuo Ohtsuki, Hajimu Mori, Toshinobu Kashiwabara, Toshio Fujisawa v. 22 i. 1 p. 60 - 97
An Improved Simulation Result for Ink-Bounded Turing Machines
by: Robert Melville v. 22 i. 1 p. 98 - 105
The Independence of Control Structures in Abstract Programming Systems
by: Gregory A. Riccardi v. 22 i. 2 p. 107 - 143
Decision Problems for Node Label Controlled Graph Grammars
by: Dirk Janssens, Grzegorz Rozenberg v. 22 i. 2 p. 144 - 177
SR(s, k) Parsers: A Class of Shift-Reduce Bounded-Context Parsers
by: David A. Workman v. 22 i. 2 p. 178 - 197
Interdependent Translation Schemes
by: Michael P. Georgeff v. 22 i. 2 p. 198 - 219
The Complexity of Decision Problems for Finite-Turn Multicounter Machines
by: Eitan M. Gurari, Oscar H. Ibarra v. 22 i. 2 p. 220 - 229
Area-Time Tradeoffs for Matrix Multiplication and Related Problems in VLSI Models
by: John E. Savage v. 22 i. 2 p. 230 - 242
Extending Lookahead for LR Parsers
by: Theodore P. Baker v. 22 i. 2 p. 243 - 259
New Hash Functions and Their Use in Authentication and Set Equality
by: Mark N. Wegman, Larry Carter v. 22 i. 3 p. 265 - 279
A Time-Luck Tradeoff in Relativized Cryptography
by: Gilles Brassard v. 22 i. 3 p. 280 - 311
On Time versus Space II. (Turing Machines)
by: Wolfgang J. Paul, Rüdiger Reischuk v. 22 i. 3 p. 312 - 327
Semantics of Probabilistic Programs
by: Dexter Kozen v. 22 i. 3 p. 328 - 350
A Time-Space Tradeoff for Sorting on Non-Oblivious Machines
by: Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa v. 22 i. 3 p. 351 - 364
On Uniform Circuit Complexity
by: Walter L. Ruzzo v. 22 i. 3 p. 365 - 383
Number of Quantifiers is Better Than Number of Tape Cells
by: Neil Immerman v. 22 i. 3 p. 384 - 406
Explicit Constructions of Linear-Sized Superconcentrators
by: Ofer Gabber, Zvi Galil v. 22 i. 3 p. 407 - 420
Division in Idealized Unit Cost RAMS
by: Janos Simon v. 22 i. 3 p. 421 - 441
Remarks on Recursion versus Diagonalization and Exponentially Difficult Problems
by: Michael Machtey, Paul Young v. 22 i. 3 p. 442 - 453
Computational Complexity of Algebraic Functions
by: Nicholas Pippenger v. 22 i. 3 p. 454 - 470
Completeness of Context-Free Grammar Forms
by: Hermann A. Maurer, Arto Salomaa, Derick Wood v. 23 i. 1 p. 1 - 10
A Complete Proof of Correctness of the Knuth-Bendix Completion Algorithm
by: Gérard P. Huet v. 23 i. 1 p. 11 - 21
Synchronous to Asynchronous Transformation of Polyautomata
by: Katsuhiko Nakamura v. 23 i. 1 p. 22 - 37
On Maximal Order for Local and Global Numerical Problems
by: Arthur G. Werschulz v. 23 i. 1 p. 38 - 48
On Correct Refinement of Programs
by: Ralph-Johan Back v. 23 i. 1 p. 49 - 68
Recursion-Closed Algebraic Theories
by: Jean H. Gallier v. 23 i. 1 p. 69 - 105
Corrigendum: Time-Space Tradeoffs for Computing Functions, Using Connectivity Properties of Their Circuits
by: Martin Tompa v. 23 i. 1 p. 106 - 106
An Information-Theoretic Approach to Time Bounds for On-Line Computation
by: Wolfgang J. Paul, Joel I. Seiferas, Janos Simon v. 23 i. 2 p. 108 - 126
An Optimal Solution to a Wire-Routing Problem
by: Martin Tompa v. 23 i. 2 p. 127 - 150
Pebbling with an Auxiliary Pushdown
by: Nicholas Pippenger v. 23 i. 2 p. 151 - 165
Maintenance of Configurations in the Plane
by: Mark H. Overmars, Jan van Leeuwen v. 23 i. 2 p. 166 - 204
Independence Results in Computer Science?
by: Deborah Joseph, Paul Young v. 23 i. 2 p. 205 - 222
Complexity of Algebraic Implementations for Abstract Data Types
by: Hartmut Ehrig, Bernd Mahr v. 23 i. 2 p. 223 - 253
Upper Bounds for Static Resource Allocation in a Distributed System
by: Nancy A. Lynch v. 23 i. 2 p. 254 - 278
Definability in Dynamic Logic
by: Albert R. Meyer, Rohit Parikh v. 23 i. 2 p. 279 - 298
Petri Nets and Regular Languages
by: Rüdiger Valk, Guy Vidal-Naquet v. 23 i. 3 p. 299 - 325
Some Observations on NP, Real Numbers and P-Selective Sets
by: Alan L. Selman v. 23 i. 3 p. 326 - 332
Theft and Conspiracy in the Take-Grant Protection Model
by: Lawrence Snyder v. 23 i. 3 p. 333 - 347
The Complexity of Restricted Regular Expressions and the Synthesis Problem for Finite Automata
by: Ernst L. Leiss v. 23 i. 3 p. 348 - 354
Query Time Versus Redundancy Trade-Offs for Range Queries
by: Michael L. Fredman, Dennis J. Volper v. 23 i. 3 p. 355 - 365
The Equivalence Problem for Two DPDA's, One of Which is a Finite-Turn or One-Counter Machine
by: Michio Oyamaguchi, Yasuyoshi Inagaki, Namio Honda v. 23 i. 3 p. 366 - 382
An Efficient Interpreter for the Lambda-Calculus
by: Luigia Carlucci Aiello, Gianfranco Prini v. 23 i. 3 p. 383 - 424

1980

A Characterization of Time Complexity by Simple Loop Programs
by: Takumi Kasai, Akeo Adachi v. 20 i. 1 p. 1 - 17
A Faster Algorithm Computing String Edit Distances
by: William J. Masek, Mike Paterson v. 20 i. 1 p. 18 - 31
Languages of R-Trivial Monoids
by: Janusz A. Brzozowski, Faith E. Fich v. 20 i. 1 p. 32 - 49
On Finding Minimal Length Superstrings
by: John Gallant, David Maier, James A. Storer v. 20 i. 1 p. 50 - 58
One-Way Weak-Stack-Counter Automata
by: Satoru Miyano v. 20 i. 1 p. 59 - 76
On the Complexity of Computing Bilinear Forms with {0, 1} Constants
by: Teofilo F. Gonzalez, Joseph JáJá v. 20 i. 1 p. 77 - 95
A Proof System for the First-Order Relational Calculus
by: Matthew Hennessy v. 20 i. 1 p. 96 - 110
Recognition of Topological Equivalence of Patterns by Array Automata
by: Paul F. Dietz, S. Rao Kosaraju v. 20 i. 1 p. 111 - 116
Time-Space Tradeoffs for Computing Functions, Using Connectivity Properties of Their Circuits
by: Martin Tompa v. 20 i. 2 p. 118 - 132
The Subgraph Homeomorphism Problem
by: Andrea S. LaPaugh, Ronald L. Rivest v. 20 i. 2 p. 133 - 149
Tree Transducers, L Systems, and Two-Way Machines
by: Joost Engelfriet, Grzegorz Rozenberg, Giora Slutzki v. 20 i. 2 p. 150 - 202
On Formulating Simultaneity for Studying Parallelism and Synchronization
by: Raymond E. Miller, Chee-Keng Yap v. 20 i. 2 p. 203 - 218
The Node-Deletion Problem for Hereditary Properties is NP-Complete
by: John M. Lewis, Mihalis Yannakakis v. 20 i. 2 p. 219 - 230
A Near-Optimal Method for Reasoning about Action
by: Vaughan R. Pratt v. 20 i. 2 p. 231 - 254
An Algorithm for Imbedding Cubic Graphs in the Torus
by: I. S. Filotti v. 20 i. 2 p. 255 - 276
Vector Addition Systems and Regular Languages
by: A. Ginzburg, Michael Yoeli v. 20 i. 3 p. 277 - 284
Adherences of Languages
by: Luc Boasson, Maurice Nivat v. 20 i. 3 p. 285 - 309
The Interaction of Integrity Constraints in an Information System
by: Jan Paredaens v. 20 i. 3 p. 310 - 329
Foundations of System Theory: The Hankel Matrix
by: Michael A. Arbib, Ernest G. Manes v. 20 i. 3 p. 330 - 378
Test Sets and Checking Words for Homomorphism Equivalence
by: Karel Culik II, Arto Salomaa v. 20 i. 3 p. 379 - 395
Coping with Errors in Binary Search Procedures
by: Ronald L. Rivest, Albert R. Meyer, Daniel J. Kleitman, Karl Winklmann, Joel Spencer v. 20 i. 3 p. 396 - 404
On the Algebra of Order
by: Daniel J. Lehmann v. 21 i. 1 p. 1 - 23
A Finite Step-Size Procedure for the F-W Method
by: Lazaros P. Mavrides v. 21 i. 1 p. 24 - 29
On DIL Schemes Simulated by D0L Schemes
by: Shigeko Seki, Youichi Kobuchi v. 21 i. 1 p. 30 - 45
Finding Patterns Common to a Set of Strings
by: Dana Angluin v. 21 i. 1 p. 46 - 62
An Efficient PQ-Graph Algorithm for Solving the Graph-Realization Problem
by: Satoru Fujishige v. 21 i. 1 p. 63 - 86
A-Transducers and the Monotonicity of IL Schemes
by: Tom Head v. 21 i. 1 p. 87 - 91
The Equivalence of RE Program Schemes and Data Flow Schemes
by: Jeffrey M. Jaffe v. 21 i. 1 p. 92 - 109
Context-Free Grammar Forms with Strict Interpretations
by: Hermann A. Maurer, Arto Salomaa, Derick Wood v. 21 i. 1 p. 110 - 135
Structure Preserving Reductions among Convex Optimization Problems
by: Giorgio Ausiello, Alessandro D'Atri, Marco Protasi v. 21 i. 1 p. 136 - 153
Computable Queries for Relational Data Bases
by: Ashok K. Chandra, David Harel v. 21 i. 2 p. 156 - 178
The Complexity of Problems in Systems of Communicating Sequential Processes
by: Richard E. Ladner v. 21 i. 2 p. 179 - 194
Lower Bounds on the Size of Sweeping Automata
by: Michael Sipser v. 21 i. 2 p. 195 - 202
An O(EVlog²V) Algorithm for the Maximal Flow Problem
by: Zvi Galil, Amnon Naamad v. 21 i. 2 p. 203 - 217
Tree-Size Bounded Alternation
by: Walter L. Ruzzo v. 21 i. 2 p. 218 - 235
Implicit Data Structures for Fast Search and Update
by: J. Ian Munro, Hendra Suwanda v. 21 i. 2 p. 236 - 250
Straight-Line Program Length as a Parameter for Complexity Analysis
by: Nancy A. Lynch v. 21 i. 3 p. 251 - 280
A Duality Theory for Decomposable Systems in a Category
by: G. Naudé v. 21 i. 3 p. 281 - 291
Multiple Equality Sets and Post Machines
by: Franz-Josef Brandenburg v. 21 i. 3 p. 292 - 316
Complexity Results for Classes of Quantificational Formulas
by: Harry R. Lewis v. 21 i. 3 p. 317 - 353
Open-Addressing Hashing with Unequal-Probability Keys
by: Gaston H. Gonnet v. 21 i. 3 p. 354 - 367
Adequacy of Decompositions of Relational Databases
by: David Maier, Alberto O. Mendelzon, Fereidoon Sadri, Jeffrey D. Ullman v. 21 i. 3 p. 368 - 379