正規表現、オートマトン、包含、型推論

SGMLに関連して割と有名な論文。"deterministic"を使っているが、決定性オートマトンの「決定性」とは違う。

• Title: Deterministic Regular Languages (1992) （実際にはたぶん1991）
• Authors: Bruggemann-Klein, Wood
• URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.6882

同じ著者（Bruggemann-Klein ＆ Wood）による、内容も同じような論文。"deterministic"じゃなくて"One-Unambiguous"という用語を使っている。

• Title: One-Unambiguous Regular Languages (1997)
• Authors: Bruggemann-Klein, Wood
• URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.3277

Hovlandの、正規表現で定義した型の包含関係を扱っているもの。型推論のアルゴリズムも載っている。One-Unambiguousの場合は、高速に処理できる。

• Title: The Inclusion Problem for Regular Expressions
• Author: Dag Hovland
• URL: http://www.ii.uib.no/~dagh/reinclusionBORA.pdf
• URL: https://bora.uib.no/handle/1956/3956

Antimirov, Mosses がintersectin付きの正規表現を扱っている。

• Title: Rewriting Extended Regular Expressions
• Authors: Antimirov, Mosses
• http://www.daimi.au.dk/PB/461/PB-461.pdf

以下は型理論ぽい。ちょっと面白そう。

• Title: Simple, Decidable Type Inference with Subtyping
• Author: Eli Gottlieb
• URL: http://arxiv.org/abs/1104.3116