Alternation as a programming paradigm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Alternation as a programming paradigm

Full text

Pdf (503 KB)

Source

International Conference on Principles and Practice of Declarative Programming archive
Proceedings of the 11th ACM SIGPLAN conference on Principles and practice of declarative programming table of contents

Coimbra, Portugal

SESSION: Integration of paradigms table of contents

Pages 61-72

Year of Publication: 2009

ISBN:978-1-60558-568-0

Authors

Wolfgang Dvořák	Technische Universität Wien, A-1040 Vienna, Austria
Georg Gottlob	Oxford University, Oxford OX1 3QD, United Kingdom
Reinhard Pichler	Technische Universität Wien, A-1040 Vienna, Austria
Stefan Woltran	Technische Universität Wien, A-1040 Vienna, Austria

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 14, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1599410.1599419 What is a DOI?

ABSTRACT

Alternation is a common tool in complexity theory, where it has been used to prove various complexity classifications. In this work, we show that it can also be used to enhance the expressive power of the imperative part of a programming language. In particular, we present Alter-Java -- an extension of Java by language constructs to express alternation, i.e., a sequence of "there exists" and "for all" statements. Moreover, we show that many practical problems have a very natural and succinct description in terms of alternation. In order to guarantee an efficient execution of such programs, we have introduced several optimizations. We also report on experiments with our implementation of Alter-Java. The results thus obtained illustrate that our alternation framework leads to competitive running times while the code to be written is significantly shorter than without this new language feature.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Abdennadher, E. Krämer, M. Saft, and M. Schmauss. JACK: A Java constraint kit. Electr. Notes Theor. Comput. Sci., 64, 2002.
	2	K.R. Apt and A. Schaerf. Search and imperative programming. In Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'97), pages 67--79, 1997.
	3	K.R. Apt and A. Schaerf. The Alma project, or how first-order logic can help us in imperative programming. In Correct System Design, volume 1710 of LNCS, pages 89--113. Springer, 1999.
	4	K.R. Apt and A. Schaerf. Programming in Alma-0, or imperative and declarative programming reconciled. In Proceedings of Frontiers of Combining Systems, pages 1--16. Research Studies Press Ltd, 2000.
	5	A.K. Chandra, D.C. Kozen, and L.J. Stockmeyer. Alternation. J. ACM, 28(1):114--133, 1981.
	6	A.K. Chandra and L.J. Stockmeyer. Alternation. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS'76), pages 98--108. IEEE Computer Society, 1976.
	7	W. Chen and D.S. Warren. Tabled evaluation with delaying for general logic programs. J. ACM, 43(1):20--74, 1996.
	8	J. Cohen. Non-deterministic algorithms. ACM Comput. Surv., 11(2):79--94, 1979.
	9	W.F. Dowling and J.H. Gallier. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. J. Log. Program., 1(3):267--284, 1984.
	10	W. Dvorák, G. Gottlob, R. Pichler, and S. Woltran. Alter-Java web page, 2009. http://www.dbai.tuwien.ac.at/proj/alternation.
	11	T. Eiter, G. Ianni, R. Schindlauer, and H. Tompits. A uniform integration of higher-order reasoning and external evaluations in answer-set programming. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI'05), pages 90--96. 2005.
	12	T. Eiter, G. Ianni, R. Schindlauer, and H. Tompits. Effective integration of declarative rules with external evaluations for semantic-web reasoning. In The Semantic Web: Research and Applications, 3rd European Semantic Web Conference (ESWC'06), volume 4011 of LNCS, pages 273--287. Springer, 2006.
	13	A.S. Fraenkel and D. Lichtenstein. Computing a perfect strategy for n*n chess requires time exponential in n. In Proceedings of the 8th Colloquium on Automata, Languages and Programming, pages 278--293. Springer, 1981.
	14	G. Gottlob, N. Leone, and F. Scarcello. A comparison of structural CSP decomposition methods. Artif. Intell., 124(2):243--282, 2000.
	15	G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci., 64(3):579--627, 2002.
	16	M. Grabmüller. Constraint Imperative Programming. Diploma thesis, Technische Universität Berlin, February 2003.
	17	M. Grabmüller. Multiparadigmen-Programmiersprachen. Research report 2003-15 in Forschungsberichte Fakultät IV -- Elektrotechnik und Informatik, Technische Universität Berlin, October 2003.
	18	R. Greenlaw, H.J. Hoover, and W.L. Ruzzo. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, 1995.
	19	D. Harel. And/or programs: A new approach to structured programming. ACM Trans. Program. Lang. Syst., 2(1):1--17, 1980.
	20	N.D. Jones and W.T. Laaser. Complete problems for deterministic polynomial time. In STOC '74: Proceedings of the 6th ACM Symposium on Theory of Computing, pages 40--46. ACM, 1974.
	21	R.E. Ladner. The circuit value problem is log space complete for P. SIGACT News, 7(1):18--20, 1975.
	22	N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scarcello. The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Log., 7(3):499--562, 2006.
	23	S. Miyano, S. Shiraishi, and T. Shoudai. A list of P -- complete problems. RIFIS Technical Report, 17:1--69, 1989.
	24	D.E. Muller, A. Saoudi, and P.E. Schupp. Weak alternating automata give a simple explanation of why most temporal and dynamic logics are decidable in exponential time. In Proceedings of the 3rd Symposium on Logic in Computer Science (LICS'88), pages 422--427. IEEE Computer Society, 1988.
	25	C.M. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
	26	T. Parr. The Definitive ANTLR Reference: Building Domain-Specific Languages. The Pragmatic Bookshelf, Raleigh, 2007.
	27	F. Pfenning, editor. Types in Logic Programming. MIT Press, 1992.
	28	A. Radensky. Toward integration of the imperative and logic programming paradigms: Horn-clause programming in the Pascal environment. SIGPLAN Not., 25(2):25--34, 1990.
	29	S. Reisch. Gobang ist PSPACE-vollständig. Acta Inf., 13:59--66, 1980.
	30	J.M. Robson. The complexity of Go. In Proceedings IFIP Congress, pages 413--417, 1983.
	31	W.L. Ruzzo. Tree-size bounded alternation. J. Comput. Syst. Sci., 21(2):218--235, 1980.
	32	K. Sagonas and P.J. Stuckey. Just enough tabling. In PPDP '04: Proceedings of the 6th ACM SIGPLAN International Conf. on Principles and Practice of Declarative Programming, pages 78--89. ACM, 2004.
	33	E.Y. Shapiro. Alternation and the computational complexity of logic programs. J. Log. Program., 1(1):19--33, 1984.
	34	M.Y. Vardi. Alternating automata and program verification. In J. van Leeuwen, editor, Computer Science Today: Recent Trends and Developments, volume 1000 of LNCS, pages 471--485. Springer, 1995.
	35	N.-F. Zhou, S. Kaneko, and K. Yamauchi. DJ: A Java-based constraint language and system. In Proceedings of the JSSST Conference, 1998.