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
Published in:
Cover of the book

2017 | OriginalPaper | Chapter

1. Introduction

Author : Wojciech Wieczorek

Published in: Grammatical Inference

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

The introductory chapter contains the different formulations of grammatical inference and indicates such formulations that will be considered in this book. Basically, the problem of grammatical inference within the present book is to be studied from machine learning and combinatorial optimization perspectives. In addition to this, the different representations of languages are assumed: deterministic and non-deterministic finite-state automata, regular expressions, and context-free grammars. As regards the machine learning approach, the design and analysis of learning experiments for comparing GI algorithms to each other or with machine learning methods will be discussed. Typical applications of the GI field are presented in this chapter as well.

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
next chapter State Merging Algorithms
Footnotes
1
This technique can also be used for algorithms that work on \(S = (S_+, S_-)\), provided that their computational complexity primarily depends on the size of \(S_+\).
 
2
The median is the number separating the higher half of a data sample, a population, or a probability distribution, from the lower half. If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values.
 
3
Scikit-learn provides a range of supervised and unsupervised learning algorithms via a consistent interface in Python. It is licensed under a permissive simplified BSD license. Its web page is http://​scikit-learn.​org/​stable/​.
 
Literature
Alpaydin E (2010) Introduction to machine learning, 2nd edn. The MIT Press
Angluin D (1976) An application of the theory of computational complexity to the study of inductive inference. PhD thesis, University of California
Book RV, Otto F (1993) String-rewriting systems. Springer, Text and Monographs in Computer Science
Bunke H, Sanfelieu A (eds) (1990) Grammatical inference. World Scientific, pp 237–290
Charikar M, Lehman E, Liu D, Panigrahy R, Prabhakaran M, Sahai A, Shelat A (2005) The smallest grammar problem. IEEE Trans Inf Theory 51(7):2554–2576MathSciNetCrossRefMATH
de la Higuera C (2005) A bibliographical study of grammatical inference. Pattern Recogn 38(9):1332–1348CrossRef
de la Higuera C (2010) Grammatical inference: learning automata and grammars. Cambridge University Press, New York, NY, USACrossRefMATH
Domaratzki M, Kisman D, Shallit J (2002) On the number of distinct languages accepted by finite automata with \(n\) states. J Autom Lang Comb 7:469–486MathSciNetMATH
Dupont P (1994) Regular grammatical inference from positive and negative samples by genetic search: the GIG method. In: Proceedings of 2nd international colloquium on grammatical inference, ICGI ’94, Lecture notes in artificial intelligence, vol 862. Springer, pp 236–245
Eyraud R, de la Higuera C, Janodet J (2007) Lars: a learning algorithm for rewriting systems. Mach Learn 66(1):7–31CrossRef
Grune D, Jacobs CJ (2008) Parsing techniques: a practical guide, 2nd edn. Springer
Heinz J, de la Higuera C, van Zaanen M (2015) Grammatical inference for computational linguistics. Synthesis lectures on human language technologies. Morgan & Claypool Publishers
Hopcroft JE, Motwani R, Ullman JD (2001) Introduction to automata theory, languages, and computation, 2nd edn. Addison-Wesley
Hunt HB III, Rosenkrantz DJ, Szymanski TG (1976) On the equivalence, containment, and covering problems for the regular and context-free languages. J Comput Syst Sci 12:222–268MathSciNetCrossRefMATH
Imada K, Nakamura K (2009) Learning context free grammars by using SAT solvers. In: Proceedings of the 2009 international conference on machine learning and applications, IEEE computer society, pp 267–272
Japkowicz N, Shah M (2011) Evaluating learning algorithms: a classification perspective. Cambridge University Press
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
Meyer AR, Stockmeyer LJ (1972) The equivalence problem for regular expressions with squaring requires exponential space. In: Proceedings of the 13th annual symposium on switching and automata theory, pp 125–129
Moore C, Eppstein D (2003) One-dimensional peg solitaire, and duotaire. In: More games of no chance. Cambridge University Press, pp 341–350
Nowakowski RJ (ed) (1996) Games of no chance. Cambridge University Press
Rozenberg G, Salomaa A (eds) (1997) Handbook of formal languages, vol 3. Beyond words. Springer
Trakhtenbrot B, Barzdin Y (1973) Finite automata: behavior and synthesis. North-Holland Publishing Company
Metadata
Title
Introduction
Author
Wojciech Wieczorek
Copyright Year
2017
Book
Grammatical Inference

Print ISBN: 978-3-319-46800-6

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

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-46801-3_1

Premium Partner

    Image Credits