检索结果-内蒙古大学图书馆

On the consistency problem for modular lattices and related structures

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION 2016年第8期26卷 1573-1595页

作者： Herrmann, Christian Tsukamoto, Yasuyuki Ziegler, Martin Tech Univ Darmstadt FB4 Schlossgartenstr 7 D-64289 Darmstadt Germany Hakuryo High Sch 2260 Amida Cho Takasago Hyogo 6760827 Japan Korea Adv Inst Sci & Technol Sch Comp 291 Daehak Ro Daejeon 34141 South Korea

The consistency problem for a class of algebraic structures asks for an algorithm to decide, for any given conjunction of equations, whether it admits a non-trivial satisfying assignment within some member of the class. For the variety of all groups, this is the complement of the triviality problem, shown undecidable by by Adyan [Algorithmic unsolvability of problems of recognition of certain properties of groups. (Russian) Dokl. Akad. Nauk SSSR (N. S.) 103 (1955) 533-535] and Rabin [Recursive unsolvability of group theoretic problems, Ann. of Math. (2) 67 (1958) 172-194]. For the class of finite groups, it amounts to the triviality problem for profinite completions, shown undecidable by Bridson and Wilton [The triviality problem for profinite completions, Invent. Math. 202 (2015) 839-874]. We derive unsolvability of the consistency problem for the class of (finite) modular lattices and various subclasses;in particular, the class of all subspace lattices of finite-dimensional vector spaces over a fixed or arbitrary field of characteristic 0 and expansions thereof, e.g. the class of subspace ortholattices of finite-dimensional Hilbert spaces. The lattice results are used to prove unsolvability of the consistency problem for (finite) rings with unit and (finite) representable relation algebras. These results in turn apply to equations between simple expressions in Grassmann-Cayley algebra and to functional and embedded multivalued dependencies in databases.

关键词： consistency problem triviality problem satisfiability decidability subspace lattice endomorphism ring relation algebra database dependencies Grassmann-Cayley algebra

来源：评论

学校读者我要写书评

暂无评论

Statistical EL is EXPTIME-complete

引用

INFORMATION PROCESSING LETTERS 2021年 169卷 106113-106113页

作者： Bednarczyk, Bartosz Univ Wroclaw Inst Comp Sci Wroclaw Poland Tech Univ Dresden Computat Log Grp Dresden Germany

We show that the consistency problem for Statistical EL ontologies, defined by Pe & ntilde;aloza and Potyka, is ExpTime-hard. Together with existing ExpTime upper bounds, we conclude ExpTime-completeness of the logic. Our proof goes via a reduction from the consistency problem for EL extended with negation of atomic concepts. (C) 2021 Elsevier B.V. All rights reserved.

关键词： consistency problem Probabilistic description logic Statistical ontologies Computational complexity

来源：评论

学校读者我要写书评

暂无评论

A multi-parameter analysis of hard problems on deterministic finite automata

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2015年第4期81卷 747-765页

作者： Fernau, Henning Heggernes, Pinar Villanger, Yngve Univ Trier Fachbereich 4 Abt Informat Wissensch D-54286 Trier Germany Univ Bergen Dept Informat N-5020 Bergen Norway

We initiate a multi-parameter analysis of two well-known NP-hard problems on deterministic finite automata (DFAs): the problem of finding a short synchronizing word, and that of finding a DFA on few states consistent with a given sample of the intended language and its complement. For both problems, we study natural parameterizations and classify them with the tools provided by Parameterized Complexity. Somewhat surprisingly, in both cases, rather simple FPT algorithms can be shown to be optimal, mostly assuming the (Strong) Exponential Time Hypothesis. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Deterministic finite automata NP-hard decision problems Synchronizing word consistency problem

来源：评论

学校读者我要写书评

暂无评论

IMAGE FORGERY USING AN ENHANCED BAYESIAN MATTING ALGORITHM

引用

INTELLIGENT AUTOMATION AND SOFT COMPUTING 2011年第3期17卷 A269-A281页

作者： Chang, I-Cheng Hsieh, Chieh-Jung Natl Dong Hwa Univ Dept Comp Sci & Informat Engn Hualien Taiwan

The development of forgery techniques for multimedia has recently become an important research topic. This paper proposes a new method to construct a tampered image based on the matting approach. Most previous matting techniques focus on the alpha estimation of the source image, since an accurate alpha matte can help with compositing the selected object into a new scene. However, the lighting conditions are inherently assumed to be coherent between the source image and the new scene. We propose an enhanced Bayesian matting method that adopts a new nearest-neighbor sampling method to extract color information. It can produce a more accurate alpha matte than previous methods, especially on the fuzzy boundaries. Furthermore, the paper deals with the lighting consistency problem. The proposed approach analyzes the color variations and shading effect and then adjusts the extracted foreground object to combine with the new background. Experimental results demonstrate the effectiveness of our method by showing the forged results of the fuzzy object and the new background under different lighting conditions.

关键词： Image forgery digital matting Bayesian approach consistency problem shading effect

来源：评论

学校读者我要写书评

暂无评论

On Sign Conditions Over Real Multivariate Polynomials

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2010年第1期44卷 195-222页

作者： Jeronimo, Gabriela Perrucci, Daniel Sabia, Juan Univ Buenos Aires Dept Matemat Fac Ciencias Exactas & Nat RA-1428 Buenos Aires DF Argentina Univ Buenos Aires Dept Ciencias Exactas RA-1428 Buenos Aires DF Argentina

We present a new probabilistic algorithm to find a finite set of points intersecting the closure of each connected component of the realization of every sign condition over a family of real polynomials defining regular hypersurfaces that intersect transversally. This enables us to show a probabilistic procedure to list all feasible sign conditions over the polynomials. In addition, we extend these results to the case of closed sign conditions over an arbitrary family of real multivariate polynomials. The complexity bounds for these procedures improve the known ones.

关键词： Real multivariate polynomials Sign conditions consistency problem Complexity

来源：评论

学校读者我要写书评

暂无评论

Version spaces and the consistency problem

引用

ARTIFICIAL INTELLIGENCE 2004年第2期156卷 115-138页

作者： Hirsh, H Mishra, N Pitt, L Stanford Univ Stanford CA 94305 USA Rutgers State Univ Piscataway NJ 08855 USA Univ Illinois Urbana IL 61801 USA

A version space is a collection of concepts consistent with a given set of positive and negative examples. Mitchell [Artificial Intelligence 18 (1982) 203-226] proposed representing a version space by its boundary sets: the maximally general (G) and maximally specific consistent concepts (S). For many simple concept classes, the size of G and S is known to grow exponentially in the number of positive and negative examples. This paper argues that previous work on alternative representations of version spaces has disguised the real question underlying version space reasoning. We instead show that tractable reasoning with version spaces turns out to depend on the consistency problem, i.e., determining if there is any concept consistent with a set of positive and negative examples. Indeed, we show that tractable version space reasoning is possible if and only if there is an efficient algorithm for the consistency problem. Our observations give rise to new concept classes for which tractable version space reasoning is now possible, e.g., 1-decision lists, monotone depth two formulas, and halfspaces. (C) 2004 Elsevier B.V. All rights reserved.

关键词： version spaces boundary sets consistency problem inductive learning

来源：评论

学校读者我要写书评

暂无评论

Equations in free inverse monoids

引用

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION 2007年第4期17卷 761-795页

作者： Deis, Timothy Meakin, John Senizergues, G. Univ Wisconsin Dept Math Madison WI 53706 USA Univ Nebraska Dept Math Lincoln NE 68588 USA Univ Bordeaux 1 Dept Comp Sci F-33405 Talence France

It is known that the problem of determining consistency of a finite system of equations in a free group or a free monoid is decidable, but the corresponding problem for systems of equations in a free inverse monoid of rank at least two is undecidable. Any solution to a system of equations in a free inverse monoid induces a solution to the corresponding system of equations in the associated free group in an obvious way, but solutions to systems of equations in free groups do not necessarily lift to solutions in free inverse monoids. In this paper, we show that the problem of determining whether a solution to a finite system of equations in a free group can be extended to a solution of the corresponding system in the associated free inverse monoid is decidable. We are able to use this to solve the consistency problem for certain classes of single-variable equations in free inverse monoids.

关键词： free inverse monoid equations consistency problem extendibility problem

来源：评论

学校读者我要写书评

暂无评论

The consistency problem in optimal control:: The degenerate case

引用

REPORTS ON MATHEMATICAL PHYSICS 2003年第2-3期51卷 171-186页

作者： Cortés, J Martínez, S Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA Univ Politecn Cataluna EUPVG Dept Matemat Aplicada 4 Vilanova i la Geltru 08800 Spain Univ Twente Syst Signals & Control Dept NL-7500 AE Enschede Netherlands CSIC Inst Matemat & Fis Fundamental E-28006 Madrid Spain

We examine the problem of the consistency of the second-order differential equations associated with optimal control problems. This problem can be treated in a presymplectic framework by means of a constraint algorithm. Two cases may arise: the regular one, already considered in the literature, and the degenerate one. The main contribution of this paper is the proposal of a discrete transition law for the optimal trajectories that reach a singular point. This discrete law respects both the geometry and the dynamical structure of the optimal control problem.

关键词： optimal control consistency problem singular points transition principle

来源：评论

学校读者我要写书评

暂无评论

Discrete Tomography of Mathematcal Quasicrystals: A Primer

引用

Electronic Notes in Discrete Mathematics 2005年 20卷 179-191页

作者： Huck, Christian Baake, Michael Langfeld, Barbara Gritzmann, Peter Lord, Katja Fakultät für Mathematik Universität Bielefeld Bielefeld Germany Zentrum Mathematik Technische Universität München München Germany

This text is a report on work progress. We introduce the class of cyclotomic model sets (mathematical quasicrystals) Λ ⊂ Z [ξn], where Z [ξn] is the ring of integers in the nth cyclotomic field Q (ξn), and discuss the corresponding decomposition, consistency and reconstruction problems of the discrete tomography of these sets. Our solution of the so-called decomposition problem also applies to the case of the square lattice Z² = Z [ξ4], which corresponds to the classical setting of discrete tomography. © 2005 Elsevier B.V. All rights reserved.

关键词： consistency problem cyclomatic model set decomposition problem discrete tomography reconstruction problem

来源：评论

学校读者我要写书评

暂无评论

Some dichotomy theorems for neural learning problems

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2004年 5卷 891-912页

作者： Schmitt, M Ruhr Univ Bochum Fak Math Lehrstuhl Math & Informat D-44780 Bochum Germany

The computational complexity of learning from binary examples is investigated for linear threshold neurons. We introduce combinatorial measures that create classes of infinitely many learning problems with sample restrictions. We analyze how the complexity of these problems depends on the values for the measures. The results are established as dichotomy theorems showing that each problem is either NP-complete or solvable in polynomial time. In particular, we consider consistency and maximum consistency problems for neurons with binary weights, and maximum consistency problems for neurons with arbitrary weights. We determine for each problem class the dividing line between the NP-complete and polynomial-time solvable problems. Moreover, all efficiently solvable problems are shown to have constructive algorithms that require no more than linear time on a random access machine model. Similar dichotomies are exhibited for neurons with bounded threshold. The results demonstrate on the one hand that the consideration of sample constraints can lead to the discovery of new efficient algorithms for non-trivial learning problems. On the other hand, hard learning problems may remain intractable even for severely restricted samples.

关键词： linear threshold neuron consistency problem computational complexity linear-time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：