Uniquely Parallel Parsable Unification Grammars (Special lssue on Selected Papers from LA Synposium)

スポンサーリンク

概要

• 論文の詳細を見る

• A uniquely parsable unification grammar (UPUG) is a formal grammar with the following features: (1) parsing is performed without backtracking, and (2) each nonterminal symbol can have arguments, and derivation and parsing processes accompany unification of terms as in Prolog (or logic programming). We newly introduce a uniquely parallel parsable unification grammar (UPPUG) by extending the framework of a UPPUG so that parallel parsing is also possible. We show that, in UPPUG, parsing can be done without backtracking in both cases of parallel and sequential reductions. We give examples of UPPUGs where a given input string can be parsed in sublinear number of steps of the length of the input by parallel reduction.

• 社団法人電子情報通信学会の論文
• 2001-01-01

著者

• Morita K

  Hiroshima Univ. Higashi‐hiroshima‐shi Jpn

• Morita Kenichi

  The Authors Are With The Faculty Of Engineering Hiroshima University

• LEE Jia

  The authors are with the Faculty of Engineering, Hiroshima University

• Lee Jia

  The Authors Are With The Faculty Of Engineering Hiroshima University

関連論文

• Uniquely Parallel Parsable Unification Grammars (Special lssue on Selected Papers from LA Synposium)
• Normal Forms for Uniquely Parsable Grammar Classes Forming the Deterministic Chomsky Hierarchy
• On the Non-existance of Rotation-Symmetric von Neumann Neighbor Number-Conserving Cellular Automata of Which the State Number is Less than Four
• A Recursive Padding Technique on Nondeterministic Cellular Automata
• Prefix Computations on Iterative Arrays with Sequential Input/Output Mode(Cellular Automata)
• A Logically Universal Number-Conserving Cellular Automaton with a Unary Table-Lookup Function(Cellular Automata)

スポンサーリンク