第七届国际计算机与信息科学数学方面会议论文集

需积分: 9 156 浏览量更新于2024-07-18 收藏 14.4MB PDF 举报

"Springer出版的《Mathematical Aspects of Computer and Information Sciences》是一本涵盖了计算机和信息科学数学方面的国际会议论文集，主要探讨该领域内的理论与应用。该书包含多个作者和编辑的贡献，旨在提供最新的研究进展和深入的学术见解。书中可能涉及的议题广泛，包括但不限于算法分析、信息安全、数据处理、计算复杂性理论等。" 这篇描述提到了一本由Springer出版社出版的学术著作，其主题聚焦于计算机和信息科学中的数学原理。该书特别强调了版权保护，指出所有权利均保留给出版商，禁止未经授权的复制、传播或任何形式的改编。此外，尽管作者、编辑和出版商尽力确保内容的准确性和真实性，但他们并不对此提供任何明示或暗示的保证，对于可能存在的错误或遗漏不承担责任。书中的内容可能来源于全球各地的研究者，如Johannes Blömer、Ilias S. Kotsireas、Temur Kutsia和Dimitris E. Simos等人。这些专家在国际会议上分享他们的研究成果，如7th International Conference, MACIS 2017，这表明书中的讨论涵盖了广泛的数学应用，可能包括密码学、编码理论、复杂性理论、数据结构、图论、概率论、统计学以及机器学习等多个子领域。 "LNCS10693"是该系列出版物的编号，表示它属于Springer的“ Lecture Notes in Computer Science”系列。这个系列始于1973年，拥有一个由国际知名学者组成的编辑委员会，其中包括来自Lancaster大学、卡内基梅隆大学、斯坦福大学、魏茨曼科学研究所等著名机构的专家。这些学者的参与确保了书中的内容具有高度的学术价值和专业性。通过这本书，读者可以深入了解计算机科学和信息科学中数学理论的应用，以及这些理论如何推动技术的发展和创新。无论是对学术研究者、研究生还是专业从业者，这本书都提供了丰富的知识资源，帮助他们理解和解决实际问题，同时也反映了该领域的最新研究趋势。

Automated Reasoning for Knot Semigroups and π-orbifold Groups of Knots 5

Obviously, Od is a factor group of Kd. Denote the generating set of Od,thatis,

the set of arcs of d,byA, and consider the natural homomorphism from the free

semigroup A

onto Od. It is easy to see that for each element g of Od, either

only words of an odd length are mapped to g or only words of an odd length

are mapped to g. Accordingly, let us say that g is an element of an odd (even)

length in the former (latter) case. A subgroup of Od consisting of elements of an

even length is called the fundamental group of the 2-fold branched cyclic cover

space of a knot [20,26]; we shall shorten this name to the two-fold group of a

knot, and shall denote the group by T d.

1.5 Putting These Constructions Together

Consider a simple example. The π-orbifold group Ot

of the trefoil knot diagram

is the dihedral group D

. The group D

naturally splits into two types of ele-

ments: 3 rotations and 3 reﬂections. The rotations form a subgroup of D

,which

is the group T t

, and which happens to be isomorphic to Z

. The reﬂections are

in a one-to-one correspondence with the arcs of the trefoil knot diagram, and the

subkei of D

consisting of reﬂections is IQt

. Generalising this example, one can

notice that every group Od splits into the subgroup Td consisting of elements of

an even length and a subkei consisting of elements of an odd length; this subkei

is related to (and in many natural examples is isomorphic to) the kei of the knot

IQd.

1.6 Other Constructions: Knot Groups and Quandles

If one considers the diagram of a knot as an oriented curve, that is, in the

context of a speciﬁc prescribed direction of travel along the curve, another pair

of algebraic constructions can be introduced (whose deﬁnitions we shall skip,

because they are not directly related to the topic of the paper). One of them is

the knot group, which is historically the ﬁrst and the best known construction

(see, for example, Sect. 6.11 in [9] or Chap. 11 in [16]). The other is the quandle

(also known as a distributive groupoid) of a knot; see, for example, [18]. These

two constructions are ‘larger’ than the ones we consider in the sense that the

π-orbifold group is a factor group of the knot group, and the kei is a factor kei

of the quandle.

2 Trivial Knots

Trivial knots can be characterised via algebaic constructions associated with

them, as the following results show.

Fact 1. The following are equivalent:

– A knot is trivial.

– The two-fold group of the knot is trivial [20,26].

– The kei of the knot is trivial [26].

6 A. Lisitsa and A. Vernitski

Fig. 1. Knot diagrams t and t

– The group of the knot is trivial [3].

– The quandle of the knot is trivial [11].

Since the π-orbifold group of a knot is ‘sandwiched’ between the two-fold group

of the knot and the group of the knot, the result also holds for π-orbifold groups.

The unusually simple structure of Kt in the example in Sect. 1 may be related

to the fact that t is a diagram of the trivial knot: it is easy to see that t is not

really ‘knotted’. A general conjecture was formulated in [25]:

Conjecture 1. A knot diagram d is a diagram of the trivial knot if and only if

Kd is an inﬁnite cyclic semigroup.

When Conjecture 1 is fully proved, it will be a natural addition to the list of

results in Fact 1. In this paper we test Conjecture 1 on a series of knot diagrams

and check how eﬃcient the technique suggested by it is at detecting trivial knots.

We conduct three types of computational experiments related to Conjecture 1:

– There are well-known examples of complicated diagrams of the trivial knot.

Given one of these diagrams d, we prove that Kd is cyclic.

– We consider a number of standard diagrams of non-trivial knots. For each of

these diagrams d, we prove that Kd is not cyclic or, equivalently, that Od is

not trivial.

– We can construct complicated diagrams of the trefoil, the simplest non-trivial

knot, by considering the sum of the standard trefoil diagram t

and of one

the complicated diagrams of the trivial knot. Given a complicated diagram d

of the trefoil, we check how eﬃciently automated reasoning proves that Kd

is not cyclic.

For comparison, in [6] using automated reasoning was proposed for unknot

detection and experiments with proving and disproving triviality of IQd were

conducted. Yet another technique was used in [7]: the problem of checking if a

knot is trivial was reduced to comparing factor quandles of the knot with families

of pre-computed quandles, and this procedure, in its turn, was reduced to SAT

solving.

2.1 How to Test if a Knot Semigroup Is Cyclic

Consider a knot diagram d with n arcs a

,...,a

.LetR

be the set of relations

read on the crossings of d, as deﬁned in Sect. 1.

Automated Reasoning for Knot Semigroups and π-orbifold Groups of Knots 7

The equational theory of the knot semigroup Kd is E

= E

∪ R

, where

is the set of equational axioms of cancellative semigroups (see them listed

explicitly in Subsect. 2.2).

By Birkhoﬀ’s completeness theorem, two words are equal if and only if their

equality can be proved by equational reasoning [1,10]; hence the following state-

ment follows (a similar statement for keis is formulated as Proposition 1 in [6]).

Proposition 1. A knot semigroup Kd of a diagram d with n arcs a

,...,a

cyclic if and only if E

∧

i=1...n−1

= a

i+1

),where denotes derivability

in the equational logic, or, equivalently in the ﬁrst-order logic with equality.

Proposition 1 suggests a practical way for experimental testing of Conjecture 1.

Given a knot diagram d (represented, for example, by its Gauss code [21]),

translate it into knot semigroup presentation R

and further into its equational

theory E

. Then apply an automated theorem prover and disprover to the

problem E

∧

i=1...n−1

= a

i+1

Note that if a complete prover is used (that is, given a valid formula it even-

tually produces a proof), the described procedure constitutes a semi-decision

algorithm: if a knot semigroup is cyclic then this fact will be eventually estab-

lished. Most common procedure for disproving is a ﬁnite model building [4],

which, given a formula, builds a ﬁnite model for the formula’s negation, thereby

refuting the original formula. Usually it is possible to ensure ﬁnite completeness

of a model builder: given a formula, it eventually produces a ﬁnite model refut-

ing it, providing such a model exists. In general, however, due to undecidability

of ﬁrst-order logic, no complete disproving procedure is available. In particular,

sometimes only inﬁnite models refuting an invalid formula exist; then the model

builder cannot build a model, even it is a complete ﬁnite model builder.

2.2 Cyclic Knot Semigroups

We applied automated theorem prover Prover9

[19] to several well-known dia-

grams of the trivial knot, and it has successfully proved that the knot semigroup

is cyclic in each case. To illustrate the approach we present the proof for the

simple diagram t in Sect. 1. The task speciﬁcation for Prover9 is divided into

assumptions and goals parts. The assumptions part includes cancellative semi-

groups axioms E

(x ∗ y) ∗ z=x∗ (y ∗ z).

x ∗ y=x ∗ z −> y=z.

y ∗ x=z ∗ x −> y=z.

and deﬁning relations for diagram t:

We have chosen Prover9 and model builder Mace4 (below), primarily to be able to

compare eﬃciency of automated reasoning with semigroups with that for involutory

quandles in [6], where the same systems were used. Otherwise the choice is not very

essential and any other automated ﬁrst order (dis)provers could be used instead.

Automated Reasoning for Knot Semigroups and π-orbifold Groups of Knots 9

Mace4 disproves the goal by ﬁnding a model in which both the cancellative

semigroup axioms and the deﬁning relations are satisﬁed, but at the same time,

the goal statement is false. The model found by Mace4 is the dihedral group D

which is the knot’s π-orbifold group, as discussed in Subsect. 1.5.

Table 2 shows the results for all standard knot diagrams with up to 9 cross-

ings. For each diagram we list the size of the model found and the time taken to

ﬁnd this model. The results presented in non-bold font are obtained by running

Mace4 with the default iterative search strategy; that is, the search for a model

starts with the size 2; if no model is found by an exhaustive search of models of a

certain size, the size is increased by 1 and the search continues. Thus, assuming

correctness of Mace4, entries in non-bold font represent smallest possible mod-

els. In all these cases the size of the model is two times the size of a smallest kei

model computed in [6]; this observation has led us to formulating the following

conjecture.

Conjecture 2. Consider a knot diagram d. Suppose the kei of d has a factor kei

of size n. Then the semigroup Kd has a factor semigroup of size 2n.

To add some more details regarding the conjecture, the smallest semigroup model

is frequently the knot’s π-orbifold group, which is frequently (see Fact 2) a dihe-

dral group, and the size of a dihedral group is two times the size of the corre-

sponding dihedral kei (that is, the kei consisting of reﬂections), which is then

the smallest kei model of the same knot diagram (Proposition 2 in [6], Theorem

3in[7]). In some other cases (for example, 8

in Table 2, which is not a 4-plat),

the knot’s π-orbifold group is not a dihedral group, but the smallest semigroup

model, which is is a factor group of the knot’s π-orbifold group, happens to be

isomorphic to the dihedral group D

. We don’t know what happens to smallest

model sizes when the smallest semigroup model is not a dihedral group and the

smallest kei model is not a dihedral kei.

Table 2 contains remarks related to Conjecture 2. The entries in bold font

represent the diagrams for which the default iterative strategy of Mace4 has

failed to ﬁnd a model in 50000 s. In this case we used Conjecture 2 to guess a

possible model size. These entries further split into three categories:

(1) the size is given with a mark

, meaning the search has been completed

successfully for this particular size, predicted by Conjecture 2; the conjecture

is conﬁrmed, but the model found is not necessarily minimal;

(2) the size is given with a mark

, meaning the search has been done for increas-

ing model sizes and ended successfully, but this was not an exhaustive search,

as a time limit was imposed on search for each size; Conjecture 2 is con-

ﬁrmed, but the model found is not necessarily minimal;

(3) the size is given with a question mark and the time is given as N/F for ‘not

found’, meaning neither search strategy has succeeded to ﬁnd a model in

50000 s; an estimated model size is given as predicted by Conjecture 2.

It is interesting to note that we could not ﬁnd a model of the predicted size

30 in any entry in the table, as Mace4 search has timed out, although for larger

剩余465页未读，继续阅读

THESUMMERE

粉丝: 23
资源: 328

第七届国际计算机与信息科学数学方面会议论文集

Communications in Computer and Information Science

Frontiers of Computer Science的word投稿模板

Communications in Computer and Information Science是什么

APOS理论的应用文献

关于机器视觉的外语参考文献

列举10个与计算机视觉相关的参考文献

springer-lncs有中文格式吗

利用Ei Village，以及Scienc Direct、 Springer Link、 wiley三个数据库中的两个，查找研究计算机软件的最新的英文期刊文献，记录检索词、检索步骤、检索结果(即共检索到多少条记录))并记录其中一条题录题录。

勤工助学管理系统的2018年之后的英文参考文献

最新资源