首页 | 本学科首页   官方微博 | 高级检索  
文章检索
  按 检索   检索词:      
出版年份:   被引次数:   他引次数: 提示:输入*表示无穷大
  收费全文   7篇
  自动化技术   7篇
  2009年   1篇
  2005年   4篇
  2002年   1篇
  1980年   1篇
排序方式: 共有7条查询结果,搜索用时 156 毫秒
1
1.
We investigate the complexity of deciding whether for minimal unsatisfiable formulas F and H there exists a variable renaming, a literal renaming or a homomorphism such that (F)=H. A variable renaming is a permutation of variables. A literal renaming is a permutation of variables which additionally replaces some of the variables by its complements. A homomorphism can be considered as a literal renaming which can map different literals to one literal.  相似文献
2.
Inspired by the notion of minimal unsatisfiable formulae we first introduce and study the class of clause minimal formulae. A CNF formula F is said to be clause minimal if any proper subformula of F is not equivalent to F. We investigate the equivalence and extension problems for clause minimal formulae. The extension problem is the question whether for two formulae F and H there is some formula G such that F+G is equivalent to H. Generally, we show that these problems are intractable. Then we discuss the complexity of these problems restricted by various parameters and constraints. In the last section we ask several open questions in this area.  相似文献
3.
We investigate the complexity of deciding whether for minimal unsatisfiable formulas F and H there exists a variable renaming, a literal renaming or a homomorphism such that (F) = H. A variable renaming is a permutation of variables. A literal renaming is a permutation of variables which additionally replaces some of the variables by its complements. A homomorphism can be considered as a literal renaming which can map different literals to one literal.  相似文献
4.
Inspired by the notion of minimal unsatisfiable formulae we first introduce and study the class of clause minimal formulae. A CNF formula F is said to be clause minimal if any proper subformula of F is not equivalent to F. We investigate the equivalence and extension problems for clause minimal formulae. The extension problem is the question whether for two formulae F and H there is some formula G such that F + G is equivalent to H. Generally, we show that these problems are intractable. Then we discuss the complexity of these problems restricted by various parameters and constraints. In the last section we ask several open questions in this area.  相似文献
5.
We say a propositional formula F in conjunctive normal form is represented by a formula H and a homomorphism φ, if φ(H)=F. A homomorphism is a mapping consisting of a renaming and an identification of literals. The deficiency of a formula is the difference between the number of clauses and the number of variables. We show that for fixed k?1 and t?1 each minimal unsatisfiable formula with deficiency k can be represented by a formula H with deficiency t and a homomorphism and such a representation can be computed in polynomial time.  相似文献
6.
Summary Asynchronous two-dimensional iterative arrays of automata will be introduced where the underlying automata are not of Moore-type but of Mealy-type. We will prove that there exists a Mealy automaton, , with only two states and one input and output for each of its four distinguished directions, such that any given Mealy-automaton can be realized by an iterative array with only for its component-machines. It is known that loop-free nets cannot be as powerful as Mealy automata; however, we will show that any Mealy automaton can be realized by a network, N, with very restrictive component machines, where no signal may pass a loop in N. Using this fact asynchronous iterative arrays can be built up with one component machine, such that any given Mealy automaton can be realized under the restriction that no signal passes a loop more than once. contains only four states and one input and output for each direction.  相似文献
7.
For propositional formulas we present a new transformation into satisfiability equivalent 3-CNF formulas of linear length. The main idea is to represent formulas as parallel-serial graphs. This is a subclass of directed acyclic multigraphs where the edges are labeled with literals and the AND operation (respectively, the OR operation) is expressed as parallel (respectively, serial) connection.  相似文献
1
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号