Hostname: page-component-7b7567c8c-tnzcf Total loading time: 0 Render date: 2026-11-12T22:06:50.700Z 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: christian.antic@icloud.com)
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.

Describing complex objects by elementary ones is a common strategy in mathematicsand science in general. In their seminal 1965 paper, Kenneth Krohn and JohnRhodes 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, wecan show in this paper that the Krohn-Rhodes Theory is applicable inAnswer Set Programming (ASP). More precisely, we recast the concept of a cascadeproduct to ASP, and prove that every program can be represented by a product ofvery simple programs, the reset and standard programs. Roughly, this impliesthat the reset and standard programs are the basic building blocks of ASP withrespect to the cascade product. In a broader sense, this paper is a first steptowards an algebraic theory of products and networks of nonmonotonic reasoningsystems based on Krohn-Rhodes Theory, aiming at important open issues in ASPand AI in general.

Keywords

Answer Set Programming (ASP)Krohn-Rhodes TheoryAutomata

Information

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Special Issue 4-5: 30th International Conference on LogicProgramming , July 2014, pp. 711 - 723
Copyright
Copyright © Cambridge University Press 2014 

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