nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

8. Applications of GI Methods in Selected Fields

verfasst von : Wojciech Wieczorek

Erschienen in: Grammatical Inference

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The present chapter is a novel contribution to the field of discrete mathematics and bio-informatics by using grammatical inference in the analysis of data. We show how to apply: (1) mathematical modeling in discovery of ordinary generating functions, (2) a decomposition-based approach: (a) to minimize boolean functions (b) to improve combinatorial game performance, and (c) in classification of biological sequences. The overall thrust of the first and third sections included in this chapter is from the author’s research publications. The detailed references are given in the bibliographical section.

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 An Algorithm Based on a Directed Acyclic Word Graph

To shift $A(z)$ to the left by m places, that is, to form the OGF for the sequence $\langle a_{m}, a_{m+1}, a_{m+2}, \ldots \rangle $ with the first m elements discarded, we subtract the first m terms and then divide by $z^m$:

$$\begin{aligned} \frac{A(z) - a_0 - \cdots - a_{m-1} z^{m-1}}{z^m} = \sum _{n \ge m} a_n z^{n-m} = \sum _{n \ge 0} a_{n+m} z^n\ . \end{aligned}$$

It is undecidable whether a CFG is ambiguous in the general case, but in many particular cases, like in the instance above, the unambiguity of a grammar may be proved.

In general, an ‘and’ term of a boolean function in a DNF is allowed to have fewer than n literals.

For this purpose (and for building the diagram in Fig. 8.3) we used Logic Friday v. 1.1.4, free software for boolean logic optimization, analysis, and synthesis. Logic Friday is developed at the University of California and it also contains the Espresso logic minimizer, which is the state-of-the-art tool for heuristic logic minimization.

Because we deal with an imbalanced data set ($|S_+| = 70$, $|S_-| = 134$), stratified 2-fold was applied. Stratified k-fold is a variation of k-fold that returns stratified folds: Each set contains approximately the same percentage of samples of each target class as the complete set.

Basten HJS (2009) The usability of ambiguity detection methods for context-free grammars. Elect Notes Theor Comput Sci 238(5):35–46CrossRef

Beerten J, Van Durme J, Gallardo R, Capriotti E, Serpell L, Rousseau F, Schymkowitz J (2015) Waltz-db: a benchmark database of amyloidogenic hexapeptides. Bioinformatics p btv027

Bender EA, Williamson SG (2006) Foundations of combinatorics with applications. Dover Books on Mathematics Series, Dover Publications

Browne C, Powley E, Whitehouse D, Lucas S, Cowling PI, Rohlfshagen P, Tavener S, Perez D, Samothrakis S, Colton S (2012) A survey of monte carlo tree search methods. IEEE Trans Comput Intell AI Games 4(1):1–43CrossRef

Buchfuhrer D, Umans C (2011) The complexity of boolean formula minimization. J Comput Syst Sci 77(1):142–153MathSciNetCrossRefMATH

Cortes C, Vapnik V (1995) Support-vector networks. Mach Learn 20:273–297MATH

Delest M (1994) Algebraic languages: a bridge between combinatorics and computer science. DIMACS: series in. Discrete Math Theor Comput Sci 24:71–87

Erickson J (1996) New toads and frogs results. In: Nowakowski RJ (ed) Games of no chance. Cambridge University Press, pp 299–310

Gimpel JF (1965) A method of producing a Boolean function having an arbitrarily prescribed prime implicant table. IEEE Trans Elect Comput 14:485–488CrossRefMATH

Graham R, Knuth D, Patashnik O (1994) Concrete mathematics: a foundation for computer science. Addison-Wesley

Hopcroft JE, Motwani R, Ullman JD (2001) Introduction to automata theory, languages, and computation, 2nd edn. Addison-Wesley

Hyatt RM (1999) Book learning—a methodology to tune an opening book automatically. ICCA J 22(1):3–12

Kuich K, Salomaa A (1985) Semirings. Springer, Languages, Automata

Lang KJ (1992) Random DFA’s can be approximately learned from sparse uniform examples. In: Proceedings of the fifth annual workshop on computational learning theory, ACM, pp 45–52

Lang KJ (1997) Merge order count. Technical report, NECI

Lang KJ, Pearlmutter BA, Price RA (1998) Results of the abbadingo one DFA learning competition and a new evidence-driven state merging algorithm. In: Proceedings of the 4th international colloquium on grammatical inference. Springer, pp 1–12

Lincke TR (2001) Strategies for the automatic construction of opening books. In: Marsland TA, Frank I (eds) Computers and games. Lecture notes in computer science, vol 2063. Springer, pp 74–86

Maurer-Stroh S, Debulpaep M, Kuemmerer N, Lopez de la Paz M, Martins IC, Reumers J, Morris KL, Copland A, Serpell L, Serrano L et al (2010) Exploring the sequence determinants of amyloid structure using position-specific scoring matrices. Nat Methods 7(3):237–242CrossRef

Nelson VP, Nagle HT, Carroll BD, Irwin JD (1995) Digital logic circuit analysis and design. Prentice-Hall

Rudell RL, Sangiovanni-Vincentelli A (1987) Multiple-valued minimization for pla optimization. IEEE Trans Comput Aided Design Integr Circuits Syst 6(5):727–750CrossRef

Solan Z, Horn D, Ruppin E, Edelman S (2005) Unsupervised learning of natural languages. Proc Nat Acad Sci U S A 102(33):11,629–11,634

Thanatipanonda TA (2008) Further hopping with toads and frogs. http://arxiv.org/pdf/0804.0640v1.pdf

Tomita E, Tanaka A, Takahashi H (2006) The worst-case time complexity for generating all maximal cliques and computational experiments. Theor Comput Sci 363(1):28–42MathSciNetCrossRefMATH

Trakhtenbrot B, Barzdin Y (1973) Finite automata: behavior and synthesis. North-Holland Publishing Company

Waterman MS (1978) Secondary structure of single-stranded nucleic acids. In: Studies on foundations and combinatorics, advances in mathematics supplementary studies, vol 1. Academic Press, pp 167–212

Wieczorek W, Nowakowski A (2015) Grammatical inference for the construction of opening books. In: Second international conference on computer science, computer engineering, and social media, CSCESM 2015, Lodz, Poland, IEEE, pp 19–22. 21–23 Sept 2015

Wieczorek W, Nowakowski A (2016) Grammatical inference in the discovery of generating functions. In: Gruca A, Brachman A, Kozielski S, Czachórski T (eds) Man–machine interactions 4, advances in intelligent systems and computing, vol 391. Springer International Publishing, pp 627–637

Wieczorek W, Unold O (2014) Induction of directed acyclic word graph in a bioinformatics task. JMLR Workshop Conf Proc 34:207–217

Wieczorek W, Unold O (2016) Use of a novel grammatical inference approach in classification of amyloidogenic hexapeptides. Comput Math Methods Med 2016, article ID 1782732

Wieczorek W, Skinderowicz R, Kozak J, Juszczuk P, Nowakowski A (2013) Selected algorithms from the 2013 Toads-and-Frogs blitz tournament. ICGA J 36(4):222–227CrossRef

Wood D (1970) A generalised normal form theorem for context-free grammars. Comput J 13(3):272–277MathSciNetCrossRefMATH

Titel: Applications of GI Methods in Selected Fields
verfasst von: Wojciech Wieczorek
Verlag: Springer International Publishing
Buch: Grammatical Inference
Print ISBN: 978-3-319-46800-6

Electronic ISBN: 978-3-319-46801-3

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-46801-3_8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"