اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSpecular sets
278
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We introduce the notion of specular sets which are subsets of groups called here specular and which form a natural generalization of free groups. These sets are an abstract generalization of the natural codings of linear involutions. We prove several results concerning the subgroups generated by return words and by maximal bifix codes in these sets.
قيم البحث
اقرأ أيضاً
The feedback arc (vertex) set problem, shortened FASP (FVSP), is to transform a given multi digraph $G=(V,E)$ into an acyclic graph by deleting as few arcs (vertices) as possible. Due to the results of Richard M. Karp in 1972 it is one of the classic
NP-complete problems. An important contribution of this paper is that the subgraphs $G_{mathrm{el}}(e)$, $G_{mathrm{si}}(e)$ of all elementary cycles or simple cycles running through some arc $e in E$, can be computed in $mathcal{O}big(|E|^2big)$ and $mathcal{O}(|E|^4)$, respectively. We use this fact and introduce the notion of the essential minor and isolated cycles, which yield a priori problem size reductions and in the special case of so called resolvable graphs an exact solution in $mathcal{O}(|V||E|^3)$. We show that weight
We present several enumeration results holding in sets of words called neutral and which satisfy restrictive conditions on the set of possible extensions of nonempty words. These formulae concern return words and bifix codes. They generalize formulae
previously known for Sturmian sets or more generally for tree sets. We also give a geometric example of this class of sets, namely the natural coding of some interval exchange transformations.
This paper addresses the problem of finding minimum forcing sets in origami. The origami material folds flat along straight lines called creases that can be labeled as mountains or valleys. A forcing set is a subset of creases that force all the othe
r creases to fold according to their labels. The result is a flat folding of the origami material. In this paper we develop a linear time algorithm that finds minimum forcing sets in one dimensional origami.
We show that the number of independent sets in cocomparability graphs can be counted in linear time, as can counting cliques in comparability graphs. By contrast, counting cliques in cocomparabilty graphs and counting independent sets in comparabilit
y graphs are #P-complete. We extend these results to counting maximal cliques and independent sets. We also consider the fixed-paramet
In a recent paper, Amini et al. introduce a general framework to prove duality theorems between special decompositions and their dual combinatorial object. They thus unify all known ad-hoc proofs in one single theorem. While this unification process
is definitely good, their main theorem remains quite technical and does not give a real insight of why some decompositions admit dual objects and why others do not. The goal of this paper is both to generalise a little this framework and to give an enlightening simple proof of its central theorem.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
