Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-25T17:23:05.805Z Has data issue: false hasContentIssue false
  • English
  • Français

On Cascade Products of Answer Set Programs

Published online by Cambridge University Press:  21 July 2014

CHRISTIAN ANTIĆ
CHRISTIAN ANTIĆ*
Affiliation:
Institute of Information Systems, Vienna University of Technology, Favoritenstraβe 9-11, A-1040 Vienna, Austria (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Describing complex objects by elementary ones is a common strategy in mathematics and science in general. In their seminal 1965 paper, Kenneth Krohn and John Rhodes showed that every finite deterministic automaton can be represented (or “emulated”) by a cascade product of very simple automata. This led to an elegant algebraic theory of automata based on finite semigroups (Krohn-Rhodes Theory). Surprisingly, by relating logic programs and automata, we can show in this paper that the Krohn-Rhodes Theory is applicable in Answer Set Programming (ASP). More precisely, we recast the concept of a cascade product to ASP, and prove that every program can be represented by a product of very simple programs, the reset and standard programs. Roughly, this implies that the reset and standard programs are the basic building blocks of ASP with respect to the cascade product. In a broader sense, this paper is a first step towards an algebraic theory of products and networks of nonmonotonic reasoning systems based on Krohn-Rhodes Theory, aiming at important open issues in ASP and AI in general.

Keywords

Answer Set Programming (ASP)Krohn-Rhodes TheoryAutomata
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Special Issue 4-5: 30th International Conference on Logic Programming , July 2014 , pp. 711 - 723
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Antić, C., Eiter, T., and Fink, M. 2013. HEX semantics via approximation fixpoint theory. In LPNMR 2013, Cabalar, P. and Cao, S. T., Eds. LNAI 8148. Springer-Verlag, Berlin/Heidelberg, 102–115.Google Scholar
Brewka, G., Eiter, T., and Fink, M. 2011. Nonmonotonic multi-context systems: A flexible approach for integrating heterogeneous knowledge sources. In Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning, Balduccini, M. and Son, T. C., Eds. LNAI 6565. Springer-Verlag, Berlin/Heidelberg, 233–258.Google Scholar
Brewka, G., Eiter, T., and Truszczyński, M. 2011. Answer set programming at a glance. Communications of the ACM 54, 12, 92–103.Google Scholar
Dao-Tran, M., Eiter, T., Fink, M., and Krennwallner, T. 2009. Modular nonmonotonic logic programming revisited. In ICLP 2009. LNCS 5649. Springer-Verlag, Berlin, 145–159.Google Scholar
Denecker, M., Marek, V. W., and Truszczyński, M. 2000. Approximations, stable operators, well-founded fixpoints and applications in nonmonotonic reasoning. In Logic-based Artificial Intelligence, Minker, J., Ed. Kluwer Academic Publishers, Dordrecht, 127–144.Google Scholar
Denecker, M., Marek, V. W., and Truszczyński, M. 2003. Uniform semantic treatment of default and autoepistemic logic. Artificial Intelligence 143, 1, 79–122.Google Scholar
Dömösi, P. and Nehaniv, C. L. 2005. Algebraic Theory of Automata Networks: An Introduction. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA.Google Scholar
Egri-Nagy, A. and Nehaniv, C. L. 2005. Algebraic hierarchical decomposition of finite state automata: Comparison of implementations for Krohn-Rhodes theory. In CIAA 2004, Domaratzki, M., Okhotin, A., Salomaa, K., and Yu, S., Eds. LNCS 3317. Springer-Verlag, Berlin/Heidelberg, 315–316.Google Scholar
Egri-Nagy, A. and Nehaniv, C. L. 2006. Making sense of the sensory data - coordinate systems by hierarchical decomposition. In KES 2006, Part III, Gabrys, B., Howlett, R. J., and Jain, L. C., Eds. LNAI 4253. Springer-Verlag, Berlin/Heidelberg, 330–340.Google Scholar
Gécseg, F. 1986. Products of Automata. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin/Heidelberg.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 3-4, 365–385.Google Scholar
Krohn, K. and Rhodes, J. 1965. Algebraic theory of machines, I. Prime decomposition theorem for finite semigroups and machines. Transactions of the American Mathematical Society 116, 450–464.CrossRefGoogle Scholar