IFIP Working Group 2.1 -- Meeting #63 Details

Contents of this page:    Local information  |  Proposed topics for discussion  |  Proposed talks

Links elsewhere:    Minutes  |  Photos (SCM)  |  Photo (EW)  |  Photos (CCM)

Local information

Hearton Hotel Kyoto
Higashi no Toin Dori Oike Agaru
Nakagyo Ku, Kyoto, Japan 604-0836
Tel +81-75-222-1300
Fax +81-75-222-1313

Necessary information for booking

Sample: Scott Macdonald, e-side, Canada 9/9 in, 9/15 out, 6 nights, twin (single use), non-smoking, vegetarian

No credit number and no advance payment is needed; but don't cancel your reservation at the last minute.

The cancellation policy: up to 24th August, no penalty; after 24th August, but at least 8 days before the meeting, you pay 30% of the cost; 7 days or less before the meeting, you pay 100%.

Estimated costs

• Room and breakfast per day, including breakfast tax: single room (16 square meter) ¥9,000; twin room (single use) ¥10,100; twin room (two people) ¥15,000.
• Lunches (¥2000), dinners (¥2500): ¥4500 per person/day.
• Meeting facilities: approximately ¥30000 per participant/week (but this depends on the number of participants).
• Excursion: the costs will be fixed later.
• Banquet: ¥6000 per person.

The costs should be paid in cash to the local host during the meeting. Alcoholic drinks are paid for personally.

Lunch is organized on Friday noon. If you intend to skip a scheduled meal, and do not want to pay for it, please indicate this in your registration, not later.

Travel instructions

The hotel has provided a map.

Schedule

There will be an excursion on Thursday afternoon (see below), and a banquet on Thursday evening.

Weather

Excursion

	longitude	latitude
Togetsu bridge	135.6776	35.01287	(35 0'46.32"N,135 40'39.35"E)
Train Station	135.6702	35.01672	(35 1'00.19"N,135 40'12.56"E)
Upper Station	135.6075	35.01324	(35 0'47.68"N,135 36'26.83"E)

The fares are 600 yen (train) and 3900 yen (boat or raft) for each. We are to hire a medium size bus to move efficiently. I don't yet know the cost of bus to be divided evenly by all.

I tried to edit kml file for google earth, but failed. So, please operate the google earth yourself.

And for those who will come down to the meeting site looking at the google earth like the superman, the coordinate of the destination (Hearton Hotel) is 35 0'42.5"N, 135 45'38.0"E.

Proposed topics for discussion

Proposed talks

Maximum Segment Sum is Back! On Two Maximum Segment Problems with Bounded Lengths Shin-Cheng Mu

It may be surprising that variations of the maximum segment sum (MSS) problem, a textbook example for the squiggolists, are still active topics for algorithm designers. I would like to examine the new developments from the view of relational program calculation.

It turns out that, while the classical MSS problem is solved by the Greedy Theorem, by applying the Thinning Theorem, we get a linear-time algorithm for MSS with upper bound on length. To derive an algorithm for the maximum segment density problem, on the other hand, we need a global notion of thinning which is stronger than the Thinning Theorem.

The concepts of left-negative and right-screw segments emerge from the search for monotonicity conditions. The efficiency of the resulting algorithms crucially relies on exploiting properties of the set of partial solutions and design efficient data structures for them.

Recounting the rationals. Twice! Roland Backhouse

Jeremy Gibbons, David Lester and Richard Bird recently published a so-called Functional Pearl on an effective way of enumerating the rationals in "Calkin-Wilf" order. They remarked that it is "not obvious" how to do the same in "Stern-Brocot" order. We show, with one algorithm, how to do both. The work is a continuation of our research on improving mathematical method reported on at the last meeting.

The torch problem Roland Backhouse

The torch (flashlight/bridge) problem is a problem of getting a number of people across a bridge with a limited capacity. A solution to the problem when the capacity of the bridge is 2 is well known. I will present a solution for the more general problem where the capacity is an input parameter. The solution has worst-case complexity O(N²) where N is the number of people. Before embarking on the problem, I was told that it is believed to be "hard" and I do not know of any other published solution. The problem is indeed surprisingly difficult to solve, but it is not "hard" in any technical sense. I strongly suspect that my solution can be improved. The conjectured improvements lead to interesting algorithmic challenges.

(with help from Diethard Michaelis and Arjan Mooij)

Representing Cyclic Structures as Nested Datatypes Varmo Vene

We show that cyclic structures, i.e., finite or possibly infinite structures with back-pointers, unwindable into possibly infinite structures, can be elegantly represented as nested datatypes. This representation is free of the various deficiencies characterizing the more naive representation as mixed-variant datatypes. It is inspired by the representation of lambda-terms as a nested datatype via the de Bruijn notation.

(Joint work with N.Ghani, M.Hamana, T.Uustalu)

Comonads for Dataflow Programming Varmo Vene

We propose a comonadic approach to dataflow (stream-based) computation. This is based on the observation that both general and causal stream functions can be characterized as coKleisli arrows of comonads and on the intuition that comonads in general must be a good means to structure context-dependent computation. In particular, we develop a generic comonadic interpreter of languages for context-dependent computation and instantiate it for stream-based computation.

(Joint work with T.Uustalu)