Skip to main content
Top

2020 | OriginalPaper | Chapter

Grammatical Inference by Answer Set Programming

Authors : Wojciech Wieczorek, Łukasz Strąk, Arkadiusz Nowakowski, Olgierd Unold

Published in: Computational Science – ICCS 2020

Publisher: Springer International Publishing

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

search-config
loading …

Abstract

In this paper, the identification of context-free grammars based on the presentation of samples is investigated. The main idea of solving this problem proposed in the literature is reformulated in two different ways: in terms of general constrains and as an answer set program. In a series of experiments, we showed that our answer set programming approach is much faster than our alternative method and the original SAT encoding method. Similarly to a pioneer work, some well-known context-free grammars have been induced correctly, and we also followed its test procedure with randomly generated grammars, making it clear that using our answer set programs increases computational efficiency. The research can be regarded as another evidence that solutions based on the stable model (answer set) semantics of logic programming may be a right choice for complex problems.

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!

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!

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!

Footnotes
1
We are aware of this imprecision. The number of words and their lengths should allow of executing a program in a reasonable amount of time. In experiments, we took two words: one example and one counter-example.
 
3
The Python scripting language is used only for generating appropriate AnsProlog facts.
 
4
This process can be done efficiently, because many ground instances can be discarded; see Chapter 4 of [6].
 
Literature
3.
go back to reference Baral, C.: Knowledge Representation, Reasoning, and Declarative Problem Solving. Cambridge University Press, New York (2003)CrossRef Baral, C.: Knowledge Representation, Reasoning, and Declarative Problem Solving. Cambridge University Press, New York (2003)CrossRef
4.
go back to reference Beerten, J., et al.: WALTZ-DB: a benchmark database of amyloidogenic hexapeptides. Bioinformatics 31(10), 1698–1700 (2015)CrossRef Beerten, J., et al.: WALTZ-DB: a benchmark database of amyloidogenic hexapeptides. Bioinformatics 31(10), 1698–1700 (2015)CrossRef
5.
go back to reference Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification and Regression Trees. Wadsworth and Brooks, Monterey (1984)MATH Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification and Regression Trees. Wadsworth and Brooks, Monterey (1984)MATH
6.
go back to reference Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer Set Solving in Practice. Morgan & Claypool Publishers, San Rafael (2012)CrossRef Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer Set Solving in Practice. Morgan & Claypool Publishers, San Rafael (2012)CrossRef
9.
go back to reference de la Higuera, C.: Grammatical Inference: Learning Automata and Grammars. Cambridge University Press, New York (2010)CrossRef de la Higuera, C.: Grammatical Inference: Learning Automata and Grammars. Cambridge University Press, New York (2010)CrossRef
10.
go back to reference Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley, Reading (2001)MATH Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley, Reading (2001)MATH
11.
go back to reference Imada, K., Nakamura, K.: Learning context free grammars by using SAT solvers. In: Proceedings of the 2009 International Conference on Machine Learning and Applications, pp. 267–272. IEEE Computer Society (2009) Imada, K., Nakamura, K.: Learning context free grammars by using SAT solvers. In: Proceedings of the 2009 International Conference on Machine Learning and Applications, pp. 267–272. IEEE Computer Society (2009)
13.
go back to reference Manning, C.D., Raghavan, P., Schütze, H.: Introduction to Information Retrieval. Cambridge University Press, Cambridge (2008)CrossRef Manning, C.D., Raghavan, P., Schütze, H.: Introduction to Information Retrieval. Cambridge University Press, Cambridge (2008)CrossRef
14.
go back to reference Maurer-Stroh, S., et al.: Exploring the sequence determinants of amyloid structure using position-specific scoring matrices. Nat. Methods 7, 237–242 (2010)CrossRef Maurer-Stroh, S., et al.: Exploring the sequence determinants of amyloid structure using position-specific scoring matrices. Nat. Methods 7, 237–242 (2010)CrossRef
16.
go back to reference Pedregosa, F., et al.: Scikit-learn: machine learning in Python. J. Mach. Learn. Res. 12, 2825–2830 (2011)MathSciNetMATH Pedregosa, F., et al.: Scikit-learn: machine learning in Python. J. Mach. Learn. Res. 12, 2825–2830 (2011)MathSciNetMATH
17.
go back to reference Salkind, N.J.: Encyclopedia of Research Design. SAGE Publications Inc., London (2010)CrossRef Salkind, N.J.: Encyclopedia of Research Design. SAGE Publications Inc., London (2010)CrossRef
18.
go back to reference Wu, T.F., Lin, C.J., Weng, R.C.: Probability estimates for multi-class classification by pairwise coupling. J. Mach. Learn. Res. 5, 975–1005 (2004)MathSciNetMATH Wu, T.F., Lin, C.J., Weng, R.C.: Probability estimates for multi-class classification by pairwise coupling. J. Mach. Learn. Res. 5, 975–1005 (2004)MathSciNetMATH
Metadata
Title
Grammatical Inference by Answer Set Programming
Authors
Wojciech Wieczorek
Łukasz Strąk
Arkadiusz Nowakowski
Olgierd Unold
Copyright Year
2020
DOI
https://doi.org/10.1007/978-3-030-50423-6_4

Premium Partner