This paper presents an approach to algebraic detection of relative form closure for a multi-fingered grasp G and gives an attention to the classification of relative form closures.Whether or not a grasp G is of relati...This paper presents an approach to algebraic detection of relative form closure for a multi-fingered grasp G and gives an attention to the classification of relative form closures.Whether or not a grasp G is of relative form closure has been verified by the geometric criterion 0?rintC[G](Xiong Y L,Xiong X R.Algebraic structure and geometric interpretation of rigid complex fixture system.IEEE Trans Autom Sci Eng,2007,4:252–264;Xiong Y L.Theory of point contact restraint and qualitative analysis of robot grasping.Sci China Ser A-Math,1994,37:629–640).Our aim is at transferring the geometric criterion into an algebraic formulation by a theorem that a grasp G is relative form closure,if,and only if the origin 0 can be represented as a positive convex combination of G.So we develop a constructive procedure called ri-simplex algorithm to find a positive convex combination of G when it has relative form closure.Form closure is considered as a special case of relative form closure,when the grasp G can affinely span the whole space,while partly relative form closure is referred to as form closed relative to a subset G1 of G.展开更多
The following problem is called the everywhere-cover problem:“Given a set of dependencies over a database scheme,is the set of dependencies explicitly given for each relation scheme equivalent to the dependencies imp...The following problem is called the everywhere-cover problem:“Given a set of dependencies over a database scheme,is the set of dependencies explicitly given for each relation scheme equivalent to the dependencies implied for that relation scheme?”It is shown that when the everywhere-cover problem has a ‘yes’ answer,examining only the dependencies explicitly given will suffice to test 3NF,BCNF and 4NF of a database scheme.But this does not hold for 2NF.Consequently,in such cases,tests of BCNF and 4NF all take polynomial time.Then a proof is given that test of 3NF of a database scheme is Co-NP-complete,and from this result it is shown that everywhere-cover is also Co-NP-complete when only functional dependencies are allowed.These results lead to doubt the truth of the well believed conjec- ture that no polynomial time algorithm for designing a Iossless BCNF database scheme is likely to exist.展开更多
基金supported by the National Natural Science Foundation of China(Grant No.51327801)the National Key Basic Research Program of China(Grant No.2013CB035803)
文摘This paper presents an approach to algebraic detection of relative form closure for a multi-fingered grasp G and gives an attention to the classification of relative form closures.Whether or not a grasp G is of relative form closure has been verified by the geometric criterion 0?rintC[G](Xiong Y L,Xiong X R.Algebraic structure and geometric interpretation of rigid complex fixture system.IEEE Trans Autom Sci Eng,2007,4:252–264;Xiong Y L.Theory of point contact restraint and qualitative analysis of robot grasping.Sci China Ser A-Math,1994,37:629–640).Our aim is at transferring the geometric criterion into an algebraic formulation by a theorem that a grasp G is relative form closure,if,and only if the origin 0 can be represented as a positive convex combination of G.So we develop a constructive procedure called ri-simplex algorithm to find a positive convex combination of G when it has relative form closure.Form closure is considered as a special case of relative form closure,when the grasp G can affinely span the whole space,while partly relative form closure is referred to as form closed relative to a subset G1 of G.
基金Supported by the National Natural Science Foundation of China.
文摘The following problem is called the everywhere-cover problem:“Given a set of dependencies over a database scheme,is the set of dependencies explicitly given for each relation scheme equivalent to the dependencies implied for that relation scheme?”It is shown that when the everywhere-cover problem has a ‘yes’ answer,examining only the dependencies explicitly given will suffice to test 3NF,BCNF and 4NF of a database scheme.But this does not hold for 2NF.Consequently,in such cases,tests of BCNF and 4NF all take polynomial time.Then a proof is given that test of 3NF of a database scheme is Co-NP-complete,and from this result it is shown that everywhere-cover is also Co-NP-complete when only functional dependencies are allowed.These results lead to doubt the truth of the well believed conjec- ture that no polynomial time algorithm for designing a Iossless BCNF database scheme is likely to exist.
