[dnsext] bi-directionality

Masataka Ohta <mohta@necom830.hpcl.titech.ac.jp> Wed, 23 February 2011 00:02 UTC

Return-Path: <dnsext-bounces@ietf.org>
X-Original-To: namedroppers-archive-gleetwall6@lists.ietf.org
Delivered-To: ietfarch-namedroppers-archive-gleetwall6@core3.amsl.com
Received: from [127.0.0.1] (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 00F493A63C9; Tue, 22 Feb 2011 16:02:00 -0800 (PST)
X-Original-To: dnsext@core3.amsl.com
Delivered-To: dnsext@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id D80DF3A63C9 for <dnsext@core3.amsl.com>; Tue, 22 Feb 2011 16:01:58 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.097
X-Spam-Level:
X-Spam-Status: No, score=-0.097 tagged_above=-999 required=5 tests=[AWL=-0.007, BAYES_00=-2.599, HELO_EQ_JP=1.244, HOST_EQ_JP=1.265]
Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6aG+S8WMEmzd for <dnsext@core3.amsl.com>; Tue, 22 Feb 2011 16:01:58 -0800 (PST)
Received: from necom830.hpcl.titech.ac.jp (necom830.hpcl.titech.ac.jp [131.112.32.132]) by core3.amsl.com (Postfix) with SMTP id DC8273A635F for <dnsext@ietf.org>; Tue, 22 Feb 2011 16:01:57 -0800 (PST)
Received: (qmail 94516 invoked from network); 23 Feb 2011 00:14:49 -0000
Received: from necom830.hpcl.titech.ac.jp (HELO ?127.0.0.1?) (131.112.32.132) by necom830.hpcl.titech.ac.jp with SMTP; 23 Feb 2011 00:14:49 -0000
Message-ID: <4D644E5E.70406@necom830.hpcl.titech.ac.jp>
Date: Wed, 23 Feb 2011 09:01:34 +0900
From: Masataka Ohta <mohta@necom830.hpcl.titech.ac.jp>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.9.2.13) Gecko/20101207 Thunderbird/3.1.7
MIME-Version: 1.0
To: dnsext@ietf.org
References: <20110216073338.7251.qmail@joyce.lan> <F21692535B1A478F95D9E3AA048E8037@ics.forth.gr> <20110216165921.GW96213@shinkuro.com> <3B90ED2E-980D-4B01-889F-447D66D0B58D@insensate.co.uk> <20110216174011.GZ96213@shinkuro.com> <20110218143653.GC84482@bikeshed.isc.org> <20110218151209.GF66684@shinkuro.com> <4D5EEE09.4080405@dougbarton.us> <20110218222950.GL74065@shinkuro.com> <4D5EF74C.9080603@dougbarton.us><20110218230905.GN74065@shinkuro.com> <4D5F270F.20401@abenaki.wabanaki.net> <199C7B2B4228461FB024E59A990DB46D@ics.forth.gr> <4D63EA86.2090206@abenaki.wabanaki.net>
In-Reply-To: <4D63EA86.2090206@abenaki.wabanaki.net>
Subject: [dnsext] bi-directionality
X-BeenThere: dnsext@ietf.org
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: DNS Extensions working group discussion list <dnsext.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/listinfo/dnsext>, <mailto:dnsext-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/dnsext>
List-Post: <mailto:dnsext@ietf.org>
List-Help: <mailto:dnsext-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/dnsext>, <mailto:dnsext-request@ietf.org?subject=subscribe>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: dnsext-bounces@ietf.org
Errors-To: dnsext-bounces@ietf.org

As Andrew requests a specific proposal, I give it also
for bi-directionality.

Hope Andrew not change his mind to say I shouldn't make
a specific proposal because it was already made 15 years
ago.

Eric Brunner-Williams wrote:

> yet we have 
> nothing (I can think of) that provides a description of (sub)string 
> (sequence of character) semantics (other than the charming property of 
> "." as construed by the UTC, of directionality, which it happily 
> associates with proximal characters, effecting directional leakage 
> across label boundaries in bidi scripts).

The problem is that bi-directionality of Unicode (and ISO 2022
extension) is not finite state but requires PDA (push down
automaton).

While PDA is fine with structured text, having PDA with plain
text is overkill.

For example, search pattern with PDA have time complexity of
O(L^3) where L is the length of text to be searched.

As I wrote recently (2/18) on IETF main ML;

https://www.ietf.org/ibin/c5i?mid=6&rid=49&gid=0&k1=933&k2=55532
Subject: Re: MHonArc mail archive line wrapping
> The assumption on line length is necessary to have multilevel
> quotation ("> ", ">> ", etc., see above) with plain text.
> We know that we can use directives of structured text such as:
>.in +3
>...
>.in -3
>when necessary.
>But, when plain text is good enough, we use plain text.

which is seemingly agreed by most, we (and DNS, especially)
shouldn't be bothered by PDA unless it is necessary.

It is not difficult to support bi-directionality with finite
state if line length is known (or known to be infinite,which
should be the case for DNS) in advance. Just spell words
backward if directionality of the words are different from
directionality of lines containing the words.

So, a specific proposal is to stick to finite state, even
though it might mean abandoning Unicode.

					Masataka Ohta
_______________________________________________
dnsext mailing list
dnsext@ietf.org
https://www.ietf.org/mailman/listinfo/dnsext