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
Erschienen in:
BFST_ED: A Novel Upper Bound Computation Framework for the Graph Edit Distance Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

A Free Energy Foundation of Semantic Similarity in Automata and Languages

verfasst von : Cewei Cui, Zhe Dang

Erschienen in: Similarity Search and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

This paper develops a free energy theory from physics including the variational principles for automata and languages and also provides algorithms to compute the energy as well as efficient algorithms for estimating the nondeterminism in a nondeterministic finite automaton. This theory is then used as a foundation to define a semantic similarity metric for automata and languages. Since automata are a fundamental model for all modern programs while languages are a fundamental model for the programs’ behaviors, we believe that the theory and the metric developed in this paper can be further used for real-word programs as well.

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
Vorheriges Kapitel Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search
Nächstes Kapitel Supermetric Search with the Four-Point Property
Fußnoten
1
The factor 2, intuitively, comes from the fact that we “stretch”, by a factor of 2, a run in finite automaton M to correspond it to a walk in graph \({\hat{M}}\). A somewhat more efficient way to compute \({{{\mathcal {E}}}}(M_V)\) is to construct an \(m\times m\) Gurevich matrix \(\mathbf{M}'\) where m is the number of states in M such that \(\mathbf{M}'_{ij}=0\) if there is no transition from \(p_i\) to \(p_j\) in M, else \(\mathbf{M}'_{ij}=\sum _{a:(p_i,a,p_j)\in T} e^{V(p_i,a,p_j)}\). Herein, \(p_1,\cdots , p_m\) are all states in M. One can show that \({{{\mathcal {E}}}}(M_V)=\ln \lambda '\) where \(\lambda '\) is the Perron-Frobenius eigenvalue of \(\mathbf{M}'\). We omit the details.
 
Literatur
1.
2.
3.
Cui, C., Dang, Z., Fischer, T.R.: Typical paths of a graph. Fundam. Inform. 110( 1–4), 95–109 (2011)MathSciNetMATH
4.
Cui, C., Dang, Z., Fischer, T.R., Ibarra, O.H.: Similarity in languages and programs. Theor. Comput. Sci. 498, 58–75 (2013)MathSciNetCrossRefMATH
5.
Cui, C., Dang, Z., Fischer, T.R., Ibarra, O.H.: Information rate of some classes of non-regular languages: an automata-theoretic approach. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014. LNCS, vol. 8634, pp. 232–243. Springer, Heidelberg (2014)
6.
Cui, C., Dang, Z., Fischer, T.R., Ibarra, O.H.: Execution information rate for some classes of automata. Inf. Comput. 246, 20–29 (2016)MathSciNetCrossRefMATH
7.
Dang, Z., Dementyev, D., Fischer, T.R., Hutton III, W.J.: Security of numerical sensors in automata. In: Drewes, F. (ed.) CIAA 2015. LNCS, vol. 9223, pp. 76–88. Springer, Heidelberg (2015)CrossRef
8.
Dehmer, M., Emmert-Streib, F., Kilian, J.: A similarity measure for graphs with low computational complexity. Appl. Math. Comput. 182(1), 447–459 (2006)MathSciNetMATH
9.
Delvenne, J.-C., Libert, A.-S.: Centrality measures and thermodynamic formalism for complex networks. Phys. Rev. E 83, 046117 (2011)CrossRef
10.
ElGhawalby, H., Hancock, E.R.: Measuring graph similarity using spectral geometry. In: Campilho, A., Kamel, M.S. (eds.) ICIAR 2008. LNCS, vol. 5112, pp. 517–526. Springer, Heidelberg (2008)CrossRef
11.
Gurevich, B.M.: A variational characterization of one-dimensional countable state gibbs random fields. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 68(2), 205–242 (1984)MathSciNetCrossRefMATH
12.
13.
Ibarra, O.H., Cui, C., Dang, Z., Fischer, T.R.: Lossiness of communication channels modeled by transducers. In: Beckmann, A., Csuhaj-Varjú, E., Meer, K. (eds.) CiE 2014. LNCS, vol. 8493, pp. 224–233. Springer, Heidelberg (2014)
14.
Koslicki, D.: Topological entropy of DNA sequences. Bioinformatics 27(8), 1061–1067 (2011)CrossRef
15.
Koslicki, D., Thompson, D.J.: Coding sequence density estimation via topological pressure. J. Math. Biol. 70(1), 45–69 (2014)MathSciNetMATH
16.
17.
Naval, S., Laxmi, V., Rajarajan, M., Gaur, M.S., Conti, M.: Employing program semantics for malware detection. IEEE Trans. Inf. Forensics Secur. 10(12), 2591–2604 (2015)CrossRef
18.
Ruelle, D.: Thermodynamic Formalism: The Mathematical Structure of Equilibrium Statistical Mechanics. Cambridge University Press/Cambridge Mathematical Library, Cambridge (2004)CrossRefMATH
19.
20.
Sarig, O.M.: Lecture notes on thermodynamic formalism for topological Markov shifts (2009)
21.
Shannon, C.E., Weaver, W.: The Mathematical Theory of Communication. University of Illinois Press, Urbana (1949)MATH
22.
Sokolsky, O., Kannan, S., Lee, I.: Simulation-based graph similarity. In: Hermanns, H., Palsberg, J. (eds.) TACAS 2006. LNCS, vol. 3920, pp. 426–440. Springer, Heidelberg (2006)CrossRef
23.
Walters, P.: An Introduction to Ergodic Theory. Graduate Texts in Mathematics. Springer, New York (1982)CrossRefMATH
24.
Metadaten
Titel
A Free Energy Foundation of Semantic Similarity in Automata and Languages
verfasst von
Cewei Cui
Zhe Dang
Copyright-Jahr
2016
Buch
Similarity Search and Applications

Print ISBN: 978-3-319-46758-0

Electronic ISBN: 978-3-319-46759-7

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-46759-7_3

Neuer Inhalt

    Bildnachweise