Download Logic Program Synthesis and Transformation: 6th International Workshop, LOPSTR'96 Stockholm, Sweden, August 28–30, 1996 Proceedings PDF

TitleLogic Program Synthesis and Transformation: 6th International Workshop, LOPSTR'96 Stockholm, Sweden, August 28–30, 1996 Proceedings
Author
LanguageEnglish
File Size18.1 MB
Total Pages333
Document Text Contents
Page 1

Lecture Notes in Computer Science
Edited by G. Goos, J. Hartmanis and J. van Leeuwen

1207

Advisory Board: W. Brauer D. Gries J. Stoer

Page 2

John Gallagher (Ed.)

Logic Program Synthesis
and Transformation

6th International Workshop, LOPSTR'96
Stockholm, Sweden, August 28-30, 1996
Proceedings

~ Springer

Page 166

160

7. new3(S) +-- append([a, b], Right, S)
8. new3(S) +-- append(Left, [a, a, b], X), append(X, Right, S)

By folding clauses (5, 6.1) using clauses (7, 8), and by folding clause 6.2 using
clause 3, we get:

9. new2([a[S]) +- new3(S)
10. new2([CIS]) +-- C~a, new2(S)

Clauses 9 and 10 are clauses of the specialized program to be derived. We have
that U2 = {}, N2 = {5,6.1,6.2}, F2 = {9, 10}, and Def3 = {7,8}, and Q3 =
Q2 u {9,10}. In the following iteration we deal with the new definition clauses 7
and 8.
Th i rd i te ra t ion . By unfolding clauses 7 and 8 we get:

11. new3([a[S]) +-- append([b], Right, S)
12. new3([a[S]) +- append([a, b], Right, S)
13. new3([C[S]) +-- append(Left, [a, a, b], Z), append(Z, Right, S)

By case split of clause 13 w.r.t, the substitution {C/a} we get:

13.1 new3([a[S]) +-- append(Left, [a, a, b], X), append(X, Right, S)
13.2 new3([C[S]) +-- C~a, append(Left, [a, a, hi, X), append(X, Right, S)

For folding clauses (11, 12, 13.1) which belong to the same packet because they
have equal heads, we introduce the following definition clauses:

14. new4(S) (-- append([b], Right, S)
15. new4(S) +-- append([a, b], Right, S)
16. new4(S) +- append(Left, [a, a, b], Z), append(X, Right, S)

By folding clauses (11, 12, 13.1) using clauses (14, 15, 16), and by folding clause
13.2 using clause 3, we get:

17. new3([a[S]) +-- new4(S)
is. ne 3([cts]) +- C # a , ne 2(S)

Clauses 17 and 18 are clauses of the specialized program to be derived. We have
that U3 = {}, N3 = {11, 12, 13.1, 13.2}, F3 = {17, 18}, Def4 = {14, 15, 16}, and
Q4 = Q3 u {17,18}. In the following iteration we deal with the new definition
clauses 14, 15, and 16.
Fou r th i te ra t ion . By unfolding clauses 14, 15, and 16 we get:

19. new4([b[S]) +-- append([ ], Right, S)
20. new4([alS]) +-- append([b], Right, S)
21. new4([aIS]) +-- append([a, b], Right, S)
22. new4([C[S]) +- append(Left, [a, a, b], Z), append(X, Right, S)

By a case split step of clause 22 w.r.t. {C/b} and then by a second case split
step w.r.t. {C/a} we get:

22.1 new4([b[S]) +- append(Left, [a, a, b], X ), append(X, Right, S)
22.2 new4([a[S]) t-- 55 a, append(Left, [a, a, b], Z) , append(X, Right, S)

Page 167

161

22.3 new4([CIS])~-- C r C ~ b, append(Left, [a, a, b],X ), appendiX, Right, S )

By simplification in the body of (22.2) we get:

23. new4([a]S]) +-- append( Le)2, [a, a, b], X), appendiX , Right, S)

For folding clauses (19, 22.1) we introduce the following definition clauses:

24. newh(S) r append([ ], Right, S)
25. newh(S) +- append(Left, [a, a, b], X), append(X, Right, S)

By folding clauses (19, 22.1) using clauses (24, 25), by folding clauses (20, 21,
23) using clauses (14, 15, 16), and by folding clause 22.3 using clause 3, we get:

26. new4([blS]) +-- newh(S)
27. new4([alS]) +-- new4(S)
28. new4([C[S]) +-- C Cb, Gee , new2(S)

Clauses 26, 27, and 28 are clauses of the specialized program to be derived. We
have that U4 = {}, Na -- {19,20,21,22.1,23,22.3}, F4 = {26,27,28}, De]5 =
{24, 25}, and Q5 = Q4 u {26, 27, 28}. In the following iteration we deal with the
new definition clauses 24 and 25.
F i f th i te ra t ion . By unfolding clauses 24 and 25 we get:

29. newh(S) +--
30. newh([a]S]) +-- append([a, b], Right, S)
31. newh([C]S]) +-- append(Left, [a, a, b], X), appendiX, Right, S)

We discard clauses 30 and 31 because they are subsumed by clause 29. We also
have that U5 = (29}, N5 -- {}, F5 = {}, De] 6 = {}, and Q6 = Q5 u (29}.
After this fifth iteration we end the application of our strategy 7) for disjunc-
tive partial deduction, because we did not introduce any extra definition clause
for performing folding steps. The final program is depicted in Figure 5(B). It
corresponds to a finite automaton which is deterministic, and in fact, clauses
9, 10, 17, 18, 26, 27, 28, and 29 correspond to the minimal finite automaton.
However, in general, our strategy does not ensure the minimality of the derived
finite automaton. We leave this problem for future research.

If in the final program we get rid of inequalities by using the cut introduction
rule, we get:

newl(S) +- new2(S)
new2([a[S]) +-!, new3(S)
ne 2([cls]) ne 2(s)
new3([alS]) ~!, new4(S)
new3([cls]) new2(S)
ne 4([bF]) ne 5(S)
new4([alS]) +--!, new4(S)
ne 4([cls]) new2(Z)
newh(S) +-

Page 332

Lecture Notes in Computer Science

For information about Vols. 1-1133

please contact your bookseller or Springer-Verlag

Vol. 1134: R. Wagner, H. Thoma (Eds.), Database and
Expert Systems Applications. Proceedings, 1996. XV, 921
pages. 1996.

Vol. 1135: B. Jonsson, J. Parrow (Eds.), Formal
Techniques in Real-Time and Fault-Tolerant Systems.
Proceedings, 1996. X, 479 pages. 1996.

Vol. 1136: J. Diaz, M. Serna (Eds.), Algorithms - ESA
'96. Proceedings, 1996. XII, 566 pages. 1996.

Vol. 1137: G. G6rz, S. HOlldobler (Eds.), KI-96: Advances
in Artificial Intelligence. Proceedings, 1996. XI, 387
pages. 1996. (Subseries LNAI).

Vol. 1138: J. Calmet, J.A. Campbell, J. Pfalzgraf (Eds.),
Artificial Intelligence and Symbolic Mathematical
Computation. Proceedings, 1996. VIII, 381 pages. 1996.

Vol. 1139: M. Hanus, M. Rogriguez-Artalejo (Eds.),
Algebraic and Logic Programming. Proceedings, 1996.
VIII, 345 pages. 1996.

Vol. 1140: H. Kuchen, S. Doaitse Swierstra (Eds.),
Programming Languages: Implementations, Logics, and
Programs. Proceedings, 1996. XI, 479 pages. 1996.

Vol. 1141: H.-M. Voigt, W. Ebeling, I. Rechenberg, H.-
P. Schwefel (Eds.), Parallel Problem Solving from Nature
- PPSN IV. Proceedings, 1996. XVII, 1.050 pages. 1996.

Vol. 1142: R.W. Hartenstein, M. Glesner (Eds.), Field-
Programmable Logic. Proceedings, 1996. X, 432 pages.
1996.

Vol. 1143: T.C. Fogarty (Ed.), Evolutionary Computing.
Proceedings, 1996. VIII, 305 pages. 1996.

Vol. 1144: J. Ponce, A. Zisserman, M. Hebert (Eds.),
Object Representation in Computer Vision. Proceedings,
1996. VIII, 403 pages. 1996.

Vol. 1145: R. Cousot, D.A. Schmidt (Eds.), Static
Analysis. Proceedings, 1996. IX, 389 pages. 1996.

Vol. 1146: E. Bertino, H. Kurth, G. Martella, E. Montolivo
(Eds.), Computer Security - ESORICS 96. Proceedings,
1996. X, 365 pages. 1996.

Vol. 1147: L. Miclet, C. de la Higuera (Eds.), Grammatical
Inference: Learning Syntax from Sentences. Proceedings,
1996. VIII, 327 pages. 1996. (Subseries LNAI).

Vol. 1148: M.C. Lin, D. Manocha (Eds.), Applied
Computational Geometry. Proceedings, 1996. VIII, 223
pages. 1996.

Vol. 1149: C. Montangero (Ed.), Software Process
Technology. Proceedings, 1996. IX, 291 pages. 1996.

Vol. 1150: A. Hlawiczka, J.G. Silva, L. Simoncini (Eds.),
Dependable Computing - EDCC-2. Proceedings, 1996.
XVI, 440 pages. 1996.

Vol. 1151: O. Bahao~lu, K. Marzullo (Eds.), Distributed
Algorithms. Proceedings, 1996. VIII, 381 pages. 1996.

Vol. 1152: T. Furuhashi, Y. Uchikawa (Eds.), Fuzzy
Logic, Neural Networks, and Evolutionary Computation.
Proceedings, 1995. VIII, 243 pages. 1996. (Subseries
LNAI).

Vol. 1153: E. Burke, P. Ross (Eds.), Practice and Theory
of Automated Timetabling. Proceedings, 1995. XIII, 381
pages. 1996.

Vol. 1154: D. Pedreschi, C. Zaniolo (Eds.), Logic in
Databases. Proceedings, 1996. X, 497 pages. 1996.

Vol. 1155: J. Roberts, U. Mocci, J. Virtamo (Eds.),
Broadbank Network Teletraffic. XXII, 584 pages. 1996.

Vol. 1156: A. Bode, J. Dongarra, T. Ludwig, V. Snnderam
(Eds.), Parallel Virtual Machine - EuroPVM '96.
Proceedings, 1996. XIV, 362 pages. 1996.

Vol. 1157: B. Thalheim (Ed.), Conceptual Modeling - ER
'96. Proceedings, 1996. XII, 489 pages. 1996.

Vol. l 158: S. Berardi, M. Coppo (Eds.), Types for Proofs
and Programs. Proceedings, 1995. X, 296 pages. 1996.

Vol. 1159: D.L. Borges, C.A.A. Kaestner (Eds.),
Advances in Artificial Intelligence. Proceedings, 1996.
XI, 243 pages. (Snbseries LNAI).

Vol. 1160: S. Arikawa, A.K. Sharma (Eds.), Algorithmic
Learning Theory. Proceedings, 1996. XVII, 337 pages.
1996. (Subseries LNAI).

Vol. 1161: O. Spaniol, C. Linnhoff-Popien, B. Meyer
(Eds.), Trends in Distributed Systems. Proceedings, 1996.
VIII, 289 pages. 1996.

Vol. 1162: D.G. Feitelson, L. Rudolph (Eds.), Job
Scheduling Strategies for Parallel Processing.
Proceedings, 1996. VIII, 291 pages. 1996.

Vol. 1163: K. Kim, T. Matsumoto (Eds.), Advances in
Cryptology - ASIACRYPT '96. Proceedings, 1996. XII,
395 pages. 1996.

Vol. 1164: K. Berquist, A. Berquist (Eds.), Managing
Information Highways. XIV, 417 pages. 1996.

Vol. 1165: L-R. Abrial, E. BOrger, H. Langmaack (Eds.),
Formal Methods for Industrial Applications. VIII, 511
pages. 1996.

Vol. 1166: M. Srivas, A. Camilleri (Eds.), Formal Methods
in Computer-Aided Design. Proceedings, 1996. IX, 470
pages. 1996.

Vol. 1167: I. Sommerville (Ed.), Software Configuration
Management. VII, 291 pages. 1996.

Vol. 1168: I. Smith, B. Faltings (Eds.), Advances in Case-
Based Reasoning. Proceedings, 1996. IX, 531 pages. 1996.
(Subseries LNAI).

Vol. 1169: M. Broy, S. Merz, K. Spies (Eds.), Formal
Systems Specification. xx in , 541 pages. 1996.

Vol. 1170: M. Nagl (Ed.), Building Tightly Integrated
Software Development Environments: The IPSEN
Approach. IX, 709 pages. 1996.

Page 333

Vol. 1171 : A. Franz, Automatic Ambiguity Resolution in
Natural Language Processing. XIX, 155 pages. 1996.
(Subseries LNAI).

Vol. 1172: J. Pieprzyk, J. Seberry (Eds.), Information
Security and Privacy. Proceedings, 1996. IX, 333 pages.
1996.

Vol. 1173: W. Rucklidge, Efficient Visual Recognition
Using the Hausdorff Distance. XIII, 178 pages. 1996.

Vol. 1174: R. Anderson (Ed.), Information Hiding.
Proceedings, 1996. VIII, 351 pages. 1996.

Vol. 1175: K.G. Jeffery, J. Kr~il, M. Barto~ek (Eds.),
SOFSEM'96: Theory and Practice of Informatics.
Proceedings, 1996. XH, 491 pages. 1996.

Vol. 1176: S. Miguet, A. Montanvert, S. Ubrda (Eds.),
Discrete Geometry for Computer Imagery. Proceedings,
1996. XI, 349 pages. 1996.

Vol. 1177: J.P. Mfiller, The Design of Intelligent Agents.
XV, 227 pages. 1996. (Subseries LNAI).

Vol. 1178: T. Asano, Y. Igarashi, H. Nagamochi, S.
Miyano, S. Suri (Eds.), Algorithms and Computation.
Proceedings, 1996. X, 448 pages. 1996.

Vol. 1179: J. Jaffar, R.H.C. Yap (Eds.), Concurrency and
Parallelism, Programming, Networking, and Security.
Proceedings, 1996. XIII, 394 pages. 1996.

Vol. 1180: V. Chandru, V. Vinay (Eds.), Foundations of
Software Technology and Theoretical Computer Science.
Proceedings, 1996. XI, 387 pages. 1996.

Vol. 1181: D. Bjr M. Broy, I.V. Pottosin (Eds.),
Perspectives of System Informatics. Proceedings, 1996.
XVII, 447 pages. 1996.

Vol. 1182: W. Hasan, Optimization of SQL Queries for
Parallel Machines. XVIII, 133 pages. 1996.

Vol. 1183: A. Wierse, G.G, Grinstein, U. Lang (Eds.),
Database Issues for Data Visualization. Proceedings,
1995. XIV, 219 pages. 1996.

Vol. 1184: J. Wa~niewski, J. Dongarra, K. Madsen,
D. Olesen (Eds.), Applied Parallel Computing.
Proceedings, 1996. XIII, 722 pages. 1996.

Vol. 1185: G. Ventre, J. Domingo-Pascuat, A. Danthine
(Eds.), Multimedia Telecommunications and
Applications. Proceedings, 1996. XII, 267 pages. 1996.

Vol. 1186: F. Afrati, P. Kolaitis (Eds.), Database Theory
- ICDT'97. Proceedings, 1997. XIII, 477 pages. 1997.

Vol. 1187: K. Schleehta, Nonmonotonic Logics. IX, 243
pages. 1997. (Subseries LNAI).

Vol. 1188: T. Martin, A.L. Ralescu (Eds.), Fuzzy Logic
in Artificial Intelligence. Proceedings, 1995. VIII, 272
pages. 1997. (Subseries LNAI).

Vol. 1189: M. Lomas (Ed.), Security Protocols.
Proceedings, 1996. VIII, 203 pages. 1997.

Vol. 1190: S. North (Ed.), Graph Drawing. Proceedings,
1996. XI, 409 pages. 1997.

Vol. 119I: V. Gaede, A. Brodsky, O~ Gfinther, D.
Srivastava, V. Vianu, M. Wallace (Eds.), Constraint
Databases and Applications. Proceedings, 1996. X, 345
pages. 1996.

Vol. 1192: M. Dam (Ed.), Analysis and Verification of
Multiple-Agent Languages. Proceedings, 1996. VIII, 435
pages. 1997.

Vol. 1193: J.P. MOiler, M.J. Wooldridge, N.R. Jennings
(Eds.), Intelligent Agents III. XV, 401 pages. 1997.
(Subseries LNAI).

Vol. 1194: M. Sipper, Evolution of Parallel Cellular
Machines. XIII, 199 pages. 1997.

Vol. 1195: R. Trappl, P. Petta (Eds.), Creating~
Personalities for Synthetic Actors. VII, 251 pages. 1997.
(Subseries LNAI).

Vol. 1196: L. Vulkov, J. Wa~niewski, P. Yalamov (Eds.),
Numerical Analysis and Its Applications. Proceedings,
1996. XIII, 608 pages. 1997.

Vol. 1197: F. d'Amore, P.G. Franeiosa, A. Marchetti-
Spaccamela (Eds.), Graph-Theoretic Concepts in
Computer Science. Proceedings, 1996. XI, 410 pages.
1997.

Vol. 1198: H.S. Nwana, N. Azarmi (Eds.), Software
Agents and Soft Computing: Towards Enhancing Machine
Intelligence. XIV, 298 pages. 1997. (Subseries LNAI).

Vol. 1199: D.K. Panda, C.B. Stunkel (Eds.),
Communication and Architectural Support for Network-
Based Parallel Computing. Proceedings, 1997. X, 269
pages. 1997.

Vol. 1200: R. Reischuk, M. Morvan (Eds.), STACS 97.
Proceedings, 1997. XII1, 614 pages. 1997.

Vol. 1201: O. Maler (Ed.), Hybrid and Real-Time
Systems. Proceedings, 1997. IX, 417 pages. 1997.

Vol. 1202: P. Kandzia, M. Klusch (Eds.), Cooperative
Information Agents. Proceedings, 1997. IX, 287 pages.
1997. (Subseries LNAI).

Vol. 1203: G. Bongiovanni, D.P. Borer, G. Di Battista
(Eds.), Algorithms and Complexity. Proceedings, 1997.
VIII, 311 pages. 1997.

Vol. 1204: H. MtJssenbOck (Ed.), Modular Programming
Languages. Proceedings, 1997. X, 379 pages. 1997.

Vo|. 1205: J. Troccaz, E. Grimson, R. M0sges (Eds.),
CVRMed-MRCAS'97. Proceedings, 1997. XIX, 834
pages. 1997.

VoL 1206: J. Bigfln, G. Chollet, G. Borgefors (Eds.),
Audio- and Video-based Biometric Person Authentication.
Proceedings, 1997. XII, 450 pages. 1997.

Vol. 1207: J. Gallagher (Ed.), Logic Program Synthesis
and Transformation. Proceedings, 1996. VII, 325 pages.
1997.

Vol. 1208: S. Ben-David (Ed.), Computational Learning
Theory. Proceedings, 1997. VIII, 331 pages. 1997.
(Subseries LNAI).

Vol. 1209: L. Cavedon, A. Rao, W. Wobcke (Eds.),
Intelligent Agent Systems. Proceedings, 1996. IX, 188
pages. 1997. (Subseries LNAI),

Vol. 1210: P. de Groote, J.R. Hindley (Eds.), Typed
Lambda Calculi and Applications. Proceedings, 1997~
VIII, 405 pages. 1997.

Vol. I211: E. Keravnou, C. Garbay, R. Baud, J. Wyatt
(Eds.), Artificial Intelligence in Medicine. Proceedings,
1997. XIII, 526 pages. 1997. (Subseries LNAI).

Vol. 1212: J. P. Bowen, M.G. Hinchey, D. Till (Eds.),
ZUM '97: The Z Formal Specification Notation.
Proceedings, 1997. X, 435 pages. 1997.

Similer Documents