Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Natural Computing
Published in: Natural Computing 1/2009

01-03-2009

Light-based string matching

Author: Mihai Oltean

Published in: Natural Computing | Issue 1/2009

Log in

Activate our intelligent search to find suitable subject content or patents.

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.
previous article Observer-invariant histopathology using genetics-based machine learning
next article An evolutionary approach for achieving scalability with general regression neural networks

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Literature
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
Feitelson DG (1988) Optical computing: a survey for computer scientists. MIT Press, Cambridge, MA
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
Metadata
Title
Light-based string matching
Author
Mihai Oltean
Publication date
01-03-2009
Publisher
Springer Netherlands
Published in
Natural Computing / Issue 1/2009
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-007-9033-0

Other articles of this Issue 1/2009

Natural Computing 1/2009 Go to the issue

OriginalPaper

Observer-invariant histopathology using genetics-based machine learning

OriginalPaper

Imitation guided learning in learning classifier systems

ReviewPaper

DNA splicing: computing by observing

OriginalPaper

An evolutionary approach for achieving scalability with general regression neural networks

OriginalPaper

Niching with derandomized evolution strategies in artificial and real-world landscapes

OriginalPaper

Intrusion detection with evolutionary learning classifier systems

Premium Partner

    Image Credits