年表 - formallang.memo

てきとう。古い論文をたどる気力がない。50年代の状況をクリアにしたいのだけど…

1946

• Post: PCP is undecidable

1954

• [REG] Huffman: DFAの最小化

1956

• [REG] Kleene: "Regular Expression"
• [REG][CFL][CSL] Chomsky: Finite-State Language(≒ NFA), Terminal Language (≒ CFG, CSG), Derivational Language(≒ L-System)

1958

• [REG] Chomsky, Miller: Finite-State Language はブール代数をなす

1959

• [REG][CFL][CSL] Chomsky: "Type0 ～ Type3 Grammar"
• [REG] Shepherdson: 2-way automaton = 1-way automaton

1962

• [CFL] Chomsky: "Pushdown Automaton" = Context Free Grammar
• [REG] Büchi: "Büchi Automaton"無限文字列に対するオートマトン
• [CFL] Cantor: CFLの曖昧性は決定不能

1963

• [CSL] Landweber: Linear-bounded Automaton ⊆ Context Sensitive Grammar

1964

• [CSL]- Kuroda: Context Sensitive Grammar ⊆ Linear-bounded Automaton
• [REG] Brzozowski: 微分による正規表現→DFA変換

1965

• [CFL] Knuth: LR(k)法
• [CFL] Kasami: CYK法 (Younger1967, Cocke1970)

1968

• [MAC] Aho: "Indexed Grammar" = Nested-Stack Automaton
• [MAC] Fischer: "Macro Grammar"
• [LSys] Lindenmayer: "L-System"
• [REG] Thatcher, Wright: WS2S = Buchi Tree Automaton

1969

• [REGT] Rabin: S2S = Muller Tree Automata = Infinite Regular Tree Language

1970

• [CFL]: Earley: Earley法
• [TT] Thatcher, Rounds: "Top-down Tree Transducer"
• [CFTG] Rounds: "Context-Free Tree Grammar"

1971

• [LSys] Lindenmayer, Rozenberg, P.G. Doucet: "0L-System"

1973

• [MAC] Rounds: Indexed/Macro は NP-complete
• [LSys] Rozenberg: "T0L-System"
• [LSys] Rozenberg: "ET0L-System"

1982

• [MAC] Damm: "IO-Hierarchy" "OI-Hierarchy"

1986

• [CFL] Tomita: GLR法