Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Natural Computing
Erschienen in: Natural Computing 1/2009

01.03.2009

Light-based string matching

verfasst von: Mihai Oltean

Erschienen in: Natural Computing | Ausgabe 1/2009

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

String matching is a very important problem in computer science. The problem consists in finding all the occurrences of a pattern P of length m in a text T of length n. We describe a special device which can do string matching by performing n−m + 1 text-to-pattern comparisons. The proposed device uses light and optical filters for performing computations. Two physical implementations are proposed. One of them uses colored glass and the other one uses polarizing filters. The strengths and the weaknesses of each method are deeply discussed.
Vorheriger Artikel Observer-invariant histopathology using genetics-based machine learning
Nächster Artikel An evolutionary approach for achieving scalability with general regression neural networks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
Born M, Wolf E (1999) Principles of optics, 7th edn. Cambridge University Press, Cambridge
Boyer R, Moore S (1977) A fast string matching algorithm. Comm Assoc Comput Mach 20:762–772
Cole R, Hariharan R, Paterson M, Zwick U (1995) Tighter lower bounds on the exact complexity of string matching. SIAM J Comput 24(1):30–45MATHCrossRefMathSciNet
Cormen TH, Leiserson CE, Rivest RR (1990) Introduction to algorithms. MIT Press, Cambridge, MA
Crochemore M, Czumaj A, Gasiniec L, Jarominek S, Lecroq T, Plandowski W, Rytter W (1994) Speeding up two string-matching algorithms. Algorithmica 5:247–267CrossRef
Damask JN (2004) Polarization optics in telecommunications. Springer Verlag, New York
Faist J (2005) Optoelectronics: silicon shines on. Nature 433:691–692CrossRef
Feitelson DG (1988) Optical computing: a survey for computer scientists. MIT Press, Cambridge, MA
Galil Z, Giancarlo R (1991) On the exact complexity of string matching: lower bounds. SIAM J Comput 6:1008–1020CrossRefMathSciNet
Galil Z, Giancarlo R (1993) On the exact complexity of string matching: upper bounds. SIAM J Comput 3:407–437MathSciNet
Goodman JW (1982) Architectural development of optical data processing systems. Aust J Electr Electron Eng 2:139–149
Guibas LJ, Odlyzko AM (1980) A new proof of the linearity of the Boyer–Moore string searching algorithm. SIAM J Comput 9:672–682MATHCrossRefMathSciNet
Hecht E (2002) Optics, 4th edn. Addison Wesley, Reading, MA
MacQueen J (1967) Some methods for classification and analysis of multivariate observations. In: LeCam LM, Neyman J (eds) Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. University of California Press, Berkeley, pp 281–297
Murphy N, Naughton TJ, Woods D, Henley B, McDermott K, Duffy E, van der Burgt PJM, Woods N (2006) Implementations of a model of physical sorting. In: Adamatzky A, Teuscher C (eds) From utopian to genuine unconventional computers workshop. Luniver Press, pp 79–100
Naughton TJ (2000) A model of computation for Fourier optical processors. In: Lessard RA, Galstian T (eds) Optics in computing, Proc SPIE, vol 4089, pp 24–34
Oltean M (2006) A light-based device for solving the Hamiltonian path problem, unconventional computing. In: Calude C et al (eds) LNCS 4135, Springer-Verlag, Berlin, pp 217–227
Paniccia M, Koehl S (2005) The silicon solution, IEEE Spectrum. IEEE Press
Reif JH, Tyagi A (1997) Efficient parallel algorithms for optical computing with the discrete Fourier transform primitive. Appl Optics 36(29):7327–7340CrossRef
Rong H, Jones R, Liu A, Cohen O, Hak D, Fang A, Paniccia M (2005a) A continuous-wave Raman silicon laser. Nature. 433:725–728CrossRef
Rong H, Liu A, Jones R, Cohen O, Hak D, Nicolaescu R, Fang A, Paniccia M (2005b) An all-silicon Raman laser. Nature. 433:292–294CrossRef
Serway RA, Jewett JW (2004) Physics for scientists and engineers, 6th edn. Brooks/Cole, Belmont, CA
Metadaten
Titel
Light-based string matching
verfasst von
Mihai Oltean
Publikationsdatum
01.03.2009
Verlag
Springer Netherlands
Erschienen in
Natural Computing / Ausgabe 1/2009
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-007-9033-0

Weitere Artikel der Ausgabe 1/2009

Natural Computing 1/2009 Zur Ausgabe

OriginalPaper

Performing DNA computation with RecA-mediated triple-stranded DNA structure

OriginalPaper

An evolutionary approach for achieving scalability with general regression neural networks

EditorialNotes

Introduction to the special issue on learning classifier systems

OriginalPaper

A learning classifier system for mazes with aliasing clones

OriginalPaper

Intrusion detection with evolutionary learning classifier systems

ReviewPaper

DNA splicing: computing by observing

Premium Partner

    Bildnachweise