Approximate string matching in sublinear expected time (English)
- New search for: Chang, W.I.
- New search for: Lawler, E.L.
- New search for: Chang, W.I.
- New search for: Lawler, E.L.
In:
Proceedings. 31st Annual Symposium on Foundations of Computer Science
;
1
;
116-124
;
1990
-
ISBN:
- Conference paper / Print
-
Title:Approximate string matching in sublinear expected time
-
Additional title:Angenäherte Zeichenkettenabstimmung in sublinear erwarteter Zeit
-
Contributors:Chang, W.I. ( author ) / Lawler, E.L. ( author )
-
Published in:
-
Publisher:
- New search for: IEEE Comput. Soc. Press
-
Place of publication:Los Alamitos
-
Publication date:1990
-
Size:9 Seiten, 42 Quellen
-
ISBN:
-
DOI:
-
Type of media:Conference paper
-
Type of material:Print
-
Language:English
-
Keywords:
-
Source:
Table of contents conference proceedings
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 0_1
-
Proceedings. 31st Annual Symposium on Foundations of Computer Science (Cat. No.90CH2925-6)| 1990
- 2
-
Algebraic methods for interactive proof systemsLund, C. / Fortnow, L. / Karloff, H. / Nisan, N. et al. | 1990
- 11
-
IP=PSPACE (interactive proof=polynomial space)Shamir, A. et al. | 1990
- 16
-
Nondeterministic exponential time has two-prover interactive protocolsBabai, L. / Fortnow, L. / Lund, C. et al. | 1990
- 26
-
A characterization of Hash P by arithmetic straight line programsBabai, L. / Fortnow, L. et al. | 1990
- 36
-
Perfectly secure message transmissionDolev, D. / Dwork, C. / Waarts, O. / Yung, M. et al. | 1990
- 46
-
Coin-flipping games immune against linear-sized coalitionsAlon, N. / Naor, M. et al. | 1990
- 55
-
Are wait-free algorithms fast?Attiya, H. / Lynch, N. / Shavit, N. et al. | 1990
- 65
-
A dining philosophers algorithm with polynomial response timeAwerbuch, B. / Saks, M. et al. | 1990
- 76
-
An approach for proving lower bounds: solution of Gilbert-Pollak's conjecture on Steiner ratioDu, D.Z. / Hwang, F.K. et al. | 1990
- 86
-
Drawing graphs in the plane with high resolutionFormann, M. / Hagerup, T. / Haralambides, J. / Kaufmann, M. / Leighton, F.T. / Simvonis, A. / Welzl, E. / Woeginger, G. et al. | 1990
- 96
-
New results on dynamic planar point locationCheng, S.W. / Janardan, R. et al. | 1990
- 106
-
The computability and complexity of optical beam tracingReif, J.H. / Tygar, J.D. / Yoshida, A. et al. | 1990
- 116
-
Approximate string matching in sublinear expected timeChang, W.I. / Lawler, E.L. et al. | 1990
- 125
-
Towards a DNA sequencing theory (learning a string)Li, M. et al. | 1990
- 135
-
On the exact complexity of string matchingColussi, L. / Galil, Z. / Giancarlo, R. et al. | 1990
- 145
-
Faster tree pattern matchingDubiner, M. / Galil, Z. / Magen, E. et al. | 1990
- 152
-
Specified precision polynomial root isolation is in NCNeff, C.A. et al. | 1990
- 163
-
A tree-partitioning technique with applications to expression evaluation and term matchingKosaraju, S.R. / Delcher, A.L. et al. | 1990
- 173
-
Efficient parallel algorithms for tree-decomposition and related problemsLagergren, J. et al. | 1990
- 186
-
Learning conjunctions of Horn clausesAngluin, D. / Frazier, M. / Pitt, L. et al. | 1990
- 193
-
Exact identification of circuits using fixed points of amplification functionsGoldman, S.A. / Kearns, M.J. / Schapire, R.E. et al. | 1990
- 203
-
On the complexity of learning from counterexamples and membership queriesMaass, W. / Turan, G. et al. | 1990
- 211
-
Separating distribution-free and mistake-bound learning models over the Boolean domainBlum, A. et al. | 1990
- 220
-
Triangulating a simple polygon in linear timeChazelle, B. et al. | 1990
- 231
-
Provably good mesh generationBern, M. / Eppstein, D. / Gilbert, J. et al. | 1990
- 242
-
Counting and cutting cycles of lines and rods in spaceChazelle, B. / Edelsbrunner, H. / Guibas, L.J. / Pollack, R. / Seidel, R. / Sharir, M. / Snoeyink, J. et al. | 1990
- 252
-
Hidden surface removal for axis-parallel polyhedraBerg, M. de / Overmars, M.H. et al. | 1990
- 264
-
A (fairly) simple circuit that (usually) sortsLeighton, T. / Plaxton, C.G. et al. | 1990
- 275
-
Fault tolerant sorting networkAssaf, S. / Upfal, E. et al. | 1990
- 285
-
Asymptotically tight bounds for computing with faulty arrays of processorsKaklamanis, C. / Karlin, A.R. / Leighton, F.T. / Milenkovic, V. / Raghavan, P. / Rao, S. / Thomborson, C. / Tsantilas, A. et al. | 1990
- 297
-
Deterministic on-line routing on area-universal networksBay, P. / Bilardi, G. et al. | 1990
- 308
-
Multiple non-interactive zero knowledge proofs based on a single random stringFeige, U. / Lapidot, D. / Shamir, A. et al. | 1990
- 318
-
Security preserving amplification of hardnessGoldreich, O. / Impagliazzo, R. / Levin, L. / Venkatesan, R. / Zuckerman, D. et al. | 1990
- 327
-
Efficiently inverting bijections given by straight line programsSturtivant, C. / Zhang, Z.L. et al. | 1990
- 335
-
Private computations over the integersChor, B. / Gereb-Graus, M. / Kushilevitz, E. et al. | 1990
- 346
-
The mixing rate of Markov chains, an isoperimetric inequality, and computing the volumeLovasz, L. / Simonovits, M. et al. | 1990
- 355
-
Exploring an unknown graphDeng, X. / Papadimitriou, C.H. et al. | 1990
- 362
-
Inferring evolutionary history from DNA sequencesKannan, S. / Warnow, T. et al. | 1990
- 372
-
PermutingFich, F.E. / Munro, J.I. / Poblete, P.V. et al. | 1990
- 382
-
Efficient distribution-free learning of probabilistic conceptsKearns, M.J. / Schapire, R.E. et al. | 1990
- 392
-
A Markovian extension of Valiant's learning modelAldous, D. / Vazirani, U. et al. | 1990
- 397
-
On threshold circuits for parityPaturi, R. / Saks, M.E. et al. | 1990
- 405
-
Robust separations in inductive inferenceFulk, M.A. et al. | 1990
- 412
-
A time-space tradeoff for Boolean matrix multiplicationAbrahamson, K. et al. | 1990
- 420
-
Communication-space tradeoffs for unrestricted protocolsBeame, P. / Tompa, M. / Yan, P. et al. | 1990
- 429
-
Time-space tradeoffs for undirected graph traversalBeame, P. / Borodin, A. / Raghavan, P. / Ruzzo, W.L. / Tompa, M. et al. | 1990
- 439
-
Constructing generalized universal traversing sequences of polynomial size for graphs with small diameterIstrail, S. et al. | 1990
- 454
-
Competitive k-server algorithmsFiat, A. / Rabani, Y. / Ravid, Y. et al. | 1990
- 464
-
Randomized online graph coloringVishwanathan, S. et al. | 1990
- 470
-
Coloring inductive graphs on-lineIrani, S. et al. | 1990
- 480
-
Online algorithms for finger searchingCole, R. / Raghunathan, A. et al. | 1990
- 492
-
Communication-optimal maintenance of replicated informationAwerbuch, B. / Cidon, I. / Kutten, S. et al. | 1990
- 503
-
Sparse partitionsAwerbuch, B. / Peleg, D. et al. | 1990
- 514
-
Network synchronization with polylogarithmic overheadAwerbuch, B. / Peleg, D. et al. | 1990
- 534
-
General weak random sourcesZuckerman, D. et al. | 1990
- 544
-
Simple construction of almost k-wise independent random variablesAlon, N. / Goldreich, O. / Hastad, J. / Peralta, R. et al. | 1990
- 554
-
Some tools for approximate 3-coloringBlum, A. et al. | 1990
- 563
-
Randomness in interactive proofsBellare, M. / Goldreich, O. / Goldwasser, S. et al. | 1990
- 574
-
Parallel linear programming in fixed dimension almost surely in constant timeAlon, N. / Megiddo, N. et al. | 1990
- 583
-
Reducing the parallel complexity of certain linear programming problemsVaidya, P.M. et al. | 1990
- 590
-
Asynchronous PRAMs are (almost) as good as synchronous PRAMsMartel, C. / Subramonian, R. / Part, A. et al. | 1990
- 600
-
Uniform memory hierarchiesAlpern, B. / Carter, L. / Feig, E. et al. | 1990
- 610
-
On the power of small-depth threshold circuitsHastad, J. / Goldmann, M. et al. | 1990
- 619
-
ON ACC and threshold circuitsYao, A.C.C. et al. | 1990
- 628
-
On interpolation by analytic functions with special properties and some weak lower bounds on the size of circuits with symmetric gatesSmolensky, R. et al. | 1990
- 632
-
Polynomial threshold functions, AC functions and spectrum normsBruck, J. / Smolensky, R. et al. | 1990
- 642
-
Faster circuits and shorter formulae for multiple addition, multiplication and symmetric Boolean functionsPaterson, M.S. / Pippenger, N. / Zwick, U. et al. | 1990
- 652
-
Deciding properties of nonregular programsHarel, D. / Raz, D. et al. | 1990
- 662
-
Decision problems for propositional linear logicLincoln, P. / Michell, J. / Scedrov, A. / Shankar, N. et al. | 1990
- 672
-
Tight bounds on the complexity of cascaded decomposition of automataMaler, O. / Pnueli, A. et al. | 1990
- 683
-
Finite-memory automataKaminski, M. / Francez, N. et al. | 1990
- 689
-
Probabilities of sentences about very sparse random graphsLynch, J.F. et al. | 1990
- 698
-
A fast algorithm for optimally increasing the edge-connectivityNaor, D. / Gusfield, D. / Martel, C. et al. | 1990
- 708
-
Augmenting graphs to meet edge-connectivity requirementsFrank, A. et al. | 1990
- 719
-
Trans-dichotomous algorithms for minimum spanning trees and shortest pathsFredman, M.L. / Willard, D.E. et al. | 1990
- 726
-
Approximation through multicommodity flowKlein, P. / Agrawal, A. / Ravi, R. / Rao, S. et al. | 1990
- 740
-
Computing with snakes in directed networks of automataEven, S. / Litman, A. / Winkler, P. et al. | 1990
- 746
-
Distributed reactive systems are hard to synthesizePneuli, A. / Rosner, R. et al. | 1990
- 758
-
Communication complexity of algebraic computationLuo, Z.Q. / Tsitsiklis, J.N. et al. | 1990
- 766
-
Bounds on tradeoffs between randomness and communication complexityCanetti, R. / Goldreich, O. et al. | 1990
- 778
-
The complexity of finding mediansToda, S. et al. | 1990
- 788
-
On the predictability of coupled automata: an allegory about chaosBuss, S. / Papadimitriou, C.H. / Tsitsiklis, N.J. et al. | 1990
- 794
-
On graph-theoretic lemmata and complexity classesPapadimitriou, C.H. et al. | 1990
- 802
-
Matrix decomposition problem is complete for the average caseGurevich, Y. et al. | 1990
- 812
-
No better ways to generate hard NP instances than picking uniformly at randomImpagliazzo, R. et al. | 1990
- 824
-
Complexity of unification in free groups and free semi-groupsKoscielski, A. / Pacholski, L. et al. | 1990
- 830
-
The lattice reduction algorithm of Gauss: an average case analysisVallee, B. / Flajolet, P. et al. | 1990
- 847
-
Simplifying nested radicals and solving polynomials by radicals in minimum depthHorng, G. / Huang, M.D.A. et al. | 1990
- 857
-
On the diameter of finite groupsBabai, L. / Hetyei, G. / Kantor, W.M. / Lubotzky, A. / Seress, A. et al. | 1990
- 871
-
Some triply-logarithmic parallel algorithmsBerkman, O. / Jaja, J. / Krishnamurthy, S. / Thurimella, R. / Vishkin, U. et al. | 1990
- 8409
-
Interpolation of sparse rational functions without knowing bounds on exponentsGrigoriev, D.Y. / Karpinski, M. / Singer, M.F. et al. | 1990