Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-14T16:19:59.597Z Has data issue: false hasContentIssue false
  • English
  • Français

The jobs puzzle: Taking on the challenge via controlled natural language processing

Published online by Cambridge University Press:  25 September 2013

ROLF SCHWITTER
ROLF SCHWITTER*
Affiliation:
Macquarie University, Department of Computing, Sydney NSW 2109, Australia (e-mail: Rolf.Schwitter@mq.edu.au)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we take on Stuart C. Shapiro's challenge of solving the Jobs Puzzle automatically and do this via controlled natural language processing. Instead of encoding the puzzle in a formal language that might be difficult to use and understand, we employ a controlled natural language as a high-level specification language that adheres closely to the original notation of the puzzle and allows us to reconstruct the puzzle in a machine-processable way and add missing and implicit information to the problem description. We show how the resulting specification can be translated into an answer set program and be processed by a state-of-the-art answer set solver to find the solutions to the puzzle.

Keywords

Controlled natural languageknowledge representationanswer set programming

References

Balduccini, M., Baral, C. and Lierler, Y. 2008. Knowledge representation and question answering. In Handbook of Knowledge Representation, van Harmelen, F., Lifschitz, V. and Porter, B., Eds. Elsevier B. V., 779–819.CrossRefGoogle Scholar
Baral, C. and Dzifcak, J. 2012. Solving puzzles described in english by automated translation to answer set programming and learning how to do that translation. In Proceedings of KR 2012, 573–577.Google Scholar
Brewka, G., Eiter, T. and Truszczyński, M. December, 2011. Answer set programming at a glance. Communications of the ACM 54, 12.Google Scholar
Finkel, R., Marek, V. W. and Truszczyński, M. 2004. Constraint Lingo: Towards high-level constraint programming. Software: Practice and Experience 34, 15, 1481–1504.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T. and Schneider, M. 2011. Potassco: The potsdam answer set solving collection. AI Communications 24, 2, 105–124.10.3233/AIC-2011-0491CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of International Logic Programming Conference and Symposium, Kowalski, R. and Bowen, K., Eds. 1070–1080.Google Scholar
Kamp, H. and Reyle, U. 1993. From Discourse to Logic: Introduction to Modeltheoretic Semantics of Natural Language, Formal Logic and Discourse Representation Theory. Kluwer, Dordrecht.Google Scholar
Lierler, Y. and Görz, G. 2006. Model generation for generalized quantifiers via answer set programming. In Proceedings of 8th Conference on Natural Language Processing (KONVENS), 101–106.Google Scholar
Lifschitz, V. 2008. What is answer set programming? In Proceedings of AAAI'08, vol. 3, 1594–1597.Google Scholar
Niemelä, I., Simons, P. and Syrjänen, T. 2000. Smodels: A system for answer set programming. In CoRR, Vol. cs.AI/0003033.Google Scholar
Schwitter, R. 2010. Controlled natural language for knowledge representation. In Proceedings of COLING 2010, 1113–1121.Google Scholar
Schwitter, R. 2012. Answer set programming via controlled natural language processing. In CNL 2012, Kuhn, T. and Fuchs, N. E., Eds., LNCS 7427, Springer, 26–43.Google Scholar
Schwitter, R., Ljungberg, A. and Hood, D. 2003. ECOLE - A look-ahead editor for a controlled language. In Proceedings of EAMT-CLAW03, May 15–17, Dublin City University, Ireland, 141–150.Google Scholar
Shapiro, S. C. 2011. The jobs puzzle: A challenge for logical expressibility and automated reasoning. In Logical Formalizations of Commonsense Reasoning, Davis, E., Doherty, P. and Erdem, E., Eds., AAAI Press, Menlo Park, CA, 96–102.Google Scholar
Shapiro, S. C. and the SNePS Implementation Group. December 8, 2010. SNePS 2.7.1 User's Manual. Department of Computer Science and Engineering, University at Buffalo, The State University of New York, Buffalo, NY.Google Scholar
Sutcliffe, G. 2009. The TPTP problem library and associated infrastructure: The FOF and CNF parts, v3.5.0. Journal of Automated Reasoning, 43, 4, 337–362.10.1007/s10817-009-9143-8CrossRefGoogle Scholar
Syrjänen, T. 2000. Lparse 1.0, User's Manual. Laboratory for Theoretical Computer Science, Helsinki University of Technology.Google Scholar
Todorova, Y. 2011. Answering questions about dynamic domains from natural language using ASP. Dissertation, Texas Tech University.Google Scholar
van Eijck, J. and Kamp, H. 2011. Discourse representation in context. In Handbook of Logic and Language, 2nd ed., van Benthem, J. and ter Meulen, A., Eds. Elsevier, 181–252.CrossRefGoogle Scholar
White, C. and Schwitter, R. 2009. An update on PENG light. In Proceedings of ALTA 2009, 80–88.Google Scholar
Wos, L., Overbeek, R., Lusk, E. and Boyle, J. 1984. Automated Reasoning: Introduction and Applications. Prentice-Hall, New Jersey.Google Scholar