Control Problem of a Class of Pushdown Automata Based on Posets and Its Application to Resolution Deductions
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, a pushdown automaton, with an infinite set of states as a partially ordered set (poset), is formulated, and its control problem of whether a given configuration can be transferred to another is discussed. For the controllability to be decidable, we take a condition the poset satisfies, that is, a condition that there are only finite number of states under the partial ordering between two given states. The control problem is decidable in polynomial time on condition the length of each pushed stack string is bounded by a constant in a given pushdown automaton. The motivation of considering the control problem comes up from the stack structure in implementing the SLD resolution deductions, in which the leftmost atom in each goal is selected and unified with some procedure name (that is, some head) of a definite clause, with the effect of the procedure name being replaced by the procedure bodies and unification constructing a pushdown automaton model for a set of definite clauses, in which leftmost selection of atom in each goal forms a stack structure and substitutions affecting goals are interpreted as states. When constructing a pushdown automaton model for an SLD resolution deduction, algebraic properties of the idempotent substitution set, which are used in unifications, are examined and utilized. The quotient set of the idempotent substitution set per renamings is adopted to present the automaton model.
- 1995-11-25
著者
関連論文
- A solid pseudopapillary tumor arising from the greater omentum followed by multiple metastases with increasing malignant potential
- Effect of Heavy Alcohol Intake on Long-term Results after Curative Resection of Hepatitis C Virus-related Hepatocellular Carcinoma
- Localized Nodular Idiopathic Retroperitoneal Fibrosis : Successful Treatment with Surgical Resection
- A Prospective Randomized Trial of the Preventive Effect of Pre-operative Transcatheter Arterial Embolization against Recurrence of Hepatocellular Carcinoma
- Negation as Failure through a Network(Computation and Computational Models)
- Semantics of Normal Goals as Acquisitors Caused by Negation as Failure
- A Combination of SLDNF Resolution with Narrowing for General Logic Programs with Equations with Respect to Extended Well-Founded Model
- Control Problem of a Class of Pushdown Automata Based on Posets and Its Application to Resolution Deductions
- Curative resection of hepatocellular carcinoma with intrabile duct tumor growth mimicking hilar bile duct carcinoma
- Shearing of Inclined Sheet Metals : Effect of Inclination Angle
- Intrahepatic cholangiocarcinoma : macroscopic type and stage classification
- Sequence Domains and Fixpoint Semantics for Logic Programs
- CASE REPORT OF SPLENIC ANEURYSM