Episciences.org
Not a member yet
6707 research outputs found
Sort by
Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
No full textThis paper focuses on the algebraic theory underlying the study of thecomplexity and the algorithms for the Constraint Satisfaction Problem (CSP). Weunify, simplify, and extend parts of the three approaches that have beendeveloped to study the CSP over finite templates -- absorption theory that wasused to characterize CSPs solvable by local consistency methods (JACM'14), andBulatov's and Zhuk's theories that were used for two independent proofs of theCSP Dichotomy Theorem (FOCS'17, JACM'20). As the first contribution we present an elementary theorem about primitivepositive definability and use it to obtain the starting points of Bulatov's andZhuk's proofs as corollaries. As the second contribution we propose andinitiate a systematic study of minimal Taylor algebras. This class of algebrasis broad enough that it suffices to verify the CSP Dichotomy Theorem on thisclass only, but still is unusually well behaved. In particular, many conceptsfrom the three approaches coincide in this class, which is in striking contrastwith the general setting. We believe that the theory initiated in this paper will eventually result ina simple and more natural proof of the Dichotomy Theorem that employs a simplerand more efficient algorithm, and will help in attacking complexity questionsin other CSP-related problems
On the finite generation of valuation semigroups on toric surfaces
No full textWe provide a combinatorial criterion for the finite generation of a valuationsemigroup associated with an ample divisor on a smooth toric surface and anon-toric valuation of maximal rank. As an application, we construct a latticepolytope such that none of the valuation semigroups of the associated polarizedtoric variety coming from one-parameter subgroups and centered at a non-toricpoint are finitely generated.Comment: 22 pages, 13 figure
On countable isotypic structures
No full textWe obtain several results concerning the concept of isotypic structures.Namely we prove that any field of finite transcendence degree over a primesubfield is defined by types; then we construct isotypic but not isomorphicstructures with countable underlying sets: totally ordered sets, fields, andgroups. This answers an old question by B. Plotkin for groups.Comment: 6 pages, Published in journal of Groups, Complexity, Cryptolog
Weighted norm inequalities for integral transforms with splitting kernels
No full textWe obtain necessary and sufficient conditions on weights for a wide class ofintegral transforms to be bounded between weighted spaces, with. The kernels of such transforms are onlyassumed to satisfy upper bounds given by products of two functions, one in eachvariable. The obtained results are applicable to a number of transforms, some of whichare included here as particular examples. Some of the new results derived hereare the characterization of weights for the boundedness of the (or Struve) transform in the case , orthe characterization of power weights for which the Laplace transform isbounded in the limiting cases or
Perceptions of 21st-century digital skills and agency among design sprint participants in Laurea UAS, Finland
No full textThis explorative study investigated students’ (N=16) perceptions before and after the study unit Digital Analytics and Consumer Insights. The studies were conducted as an intensive hybrid five-day design sprint, a variant of project- and problem-based learning. An online questionnaire with a 5-point Likert scale was used for data collection. The findings indicate that the intervention improved perceptions of most studied digital “hard skills” (8/11 claims). Out of twelve 21st-century “soft skills” claims, perceptions were high initially and improved significantly for critical thinking and systematic problem-solving claims during the design sprint. The agency scores showed a slight improvement but no significant difference. Face-to-face groups would be willing to recommend the sprint method more for peers than online groups. In the era of global turbulence and artificial intelligence, in addition to hard skills, soft skills like communication, teamwork, problem-solving and project management are in demand by employers. According to LinkedIn data in 2/2024, adaptability is the most demanded skill. In addition to traditional subjects, the pedagogical methods in higher education should better support the development of 21st-century skills
SKdV, SmKdV flows and their supersymmetric gauge-Miura transformations
No full textThe construction of Integrable Hierarchies in terms of zero curvaturerepresentation provides a systematic construction for a series of integrablenon-linear evolution equations (flows) which shares a common affine Liealgebraic structure. The integrable hierarchies are then classified in terms ofa decomposition of the underlying affine Lie algebra intograded subspaces defined by a grading operator . In this paper we shalldiscuss explicitly the simplest case of the affine Kac-Moodyalgebra within the principal gradation given rise to the KdV and mKdVhierarchies and extend to supersymmetric models. It is known that the positive mKdV sub-hierachy is associated to somepositive odd graded abelian subalgebra with elements denoted by .Each of these elements in turn, defines a time evolution equation according totime . An interesting observation is that for negative grades, thezero curvature representation allows both, even or odd sub-hierarchies. In bothcases, the flows are non-local leading to integro-differential equations.Whilst positive and negative odd sub-hierarchies admit zero vacuum solutions,the negative even admits strictly non-zero vacuum solutions. Soliton solutionscan be constructed by gauge transforming the zero curvature from the vacuuminto a non trivial configuration (dressing method). Inspired by the dressing transformation method, we have constructed agauge-Miura transformation mapping mKdV into KdV flows. Interesting new resultsconcerns the negative grade sector of the mKdV hierarchy in which a doubledegeneracy of flows (odd and its consecutive even) of mKdV are mapped into asingle odd KdV flow. These results are extended to supersymmetric hierarchiesbased upon the affine super-algebra.Comment: 22 pages Late
A Strong Bisimulation for a Classical Term Calculus
No full textWhen translating a term calculus into a graphical formalism many inessentialdetails are abstracted away. In the case of -calculus translated toproof-nets, these inessential details are captured by a notion of equivalenceon -terms known as -equivalence, in both theintuitionistic (due to Regnier) and classical (due to Laurent) cases. Thepurpose of this paper is to uncover a strong bisimulation behind-equivalence, as formulated by Laurent for Parigot's-calculus. This is achieved by introducing a relation ,defined over a revised presentation of -calculus we dub \LambdaM. More precisely, we first identify the reasons behind Laurent's-equivalence on -terms failing to be a strongbisimulation. Inspired by Laurent's \emph{Polarized Proof-Nets}, this leads usto distinguish multiplicative and exponential reduction steps on terms. Second,we enrich the syntax of to allow us to track the exponentialoperations. These technical ingredients pave the way towards a strongbisimulation for the classical case. We introduce a calculus and arelation that we show to be a strong bisimulation with respect toreduction in , ie. two -equivalent terms have the exact samereduction semantics, a result which fails for Regnier's-equivalence in -calculus as well as for Laurent's-equivalence in . Although is formulatedover an enriched syntax and hence is not strictly included in Laurent's, we show how it can be seen as a restriction of it.Comment: arXiv admin note: text overlap with arXiv:1906.0937
The addition of temporal neighborhood makes the logic of prefixes and sub-intervals EXPSPACE-complete
No full textA classic result by Stockmeyer gives a non-elementary lower bound to theemptiness problem for star-free generalized regular expressions. This result isintimately connected to the satisfiability problem for interval temporal logic,notably for formulas that make use of the so-called chop operator. Such anoperator can indeed be interpreted as the inverse of the concatenationoperation on regular languages, and this correspondence enables reductionsbetween non-emptiness of star-free generalized regular expressions andsatisfiability of formulas of the interval temporal logic of chop under thehomogeneity assumption. In this paper, we study the complexity of thesatisfiability problem for suitable weakenings of the chop interval temporallogic, that can be equivalently viewed as fragments of Halpern and Shohaminterval logic. We first consider the logic featuringmodalities , for \emph{begins}, corresponding to the prefix relation onpairs of intervals, and , for \emph{during}, corresponding to the infixrelation. The homogeneous models of naturally correspond tolanguages defined by restricted forms of regular expressions, that use union,complementation, and the inverses of the prefix and infix relations. Such afragment has been recently shown to be PSPACE-complete . In this paper, westudy the extension with the temporal neighborhood modality (corresponding to the Allen relation \emph{Meets}), and prove that itincreases both its expressiveness and complexity. In particular, we show thatthe resulting logic is EXPSPACE-complete
Historical Documents and Automatic Text Recognition: Introduction
No full textWith this special issue of the Journal of Data Mining and Digital Humanities (JDMDH), we bringtogether in one single volume several experiments, projects and reflections related to automatic textrecognition applied to historical documents. More and more research projects now include automatic text acquisition in their data processing chain, and this is true not only for projects focussed on Digital or Computational Humanities but increasingly also for those that are simply using existing digital tools as the means to an end. The increasing use of this technology has led to an automation of tasks that affects the role of the researcher in the textual production process. This new data-intensive practice makes it urgent to collect and harmonise the corpora necessary for the constitution of training sets, but also to make them available for exploitation. This special issue is therefore an opportunity to present articles combining philological and technical questions to make a scientific assessment of the use of automatic text recognition for ancient documents, its results, its contributions and the new practices induced by its use in the process of editing and exploring texts. We hope that practical aspects will be questioned on this occasion, while raising methodological challenges and its impact on research data.The special issue on Automatic Text Recognition (ATR) is therefore dedicated to providing a comprehensive overview of the use of ATR in the humanities field, particularly concerning historical documents in the early 2020s. This issue presents a fusion of engineering and philological aspects, catering to both beginners and experienced users interested in launching projects with ATR. The collection encompasses a diverse array of approaches, covering topics such as data creation or collection for training generic models, reaching specific objectives, technical and HTR machine architecture, segmentation methods, and image processing
Robustesse de l'algorithme Data-Driven Identification avec des données d'entrée incomplètes
No full textIdentifying the mechanical response of a material without presupposing any constitutive equation is possible thanks to the Data-Driven Identification algorithm developed by the authors. It allows to measure stresses from displacement fields and forces applied to a given structure; the peculiarity of the technique is the absence of underlying constitutive equation. In the case of real experiments, the algorithm has been successfully applied on a perforated elastomer sheet deformed under large strain. Displacements are gathered with Digital Image Correlation and net forces with a load cell. However, those real data are incomplete for two reasons: some displacement values, close to the edges or in a noise-affected area, are missing and the force information is incomplete with respect to the original DDI algorithm requirements. The present study proves that with appropriate data handling, stress fields can be identified in a robust manner. The solution relies on recovering those missing data in a way that no assumption, except the balance of linear momentum, has to be made. The influence of input parameters of the method is also discussed. The overall study is conducted on synthetic data: perfect and incomplete data are used to prove robustness of the proposed solutions. Therefore, the paper can be considered as a practical guide for implementing the DDI method.L'identification de la réponse mécanique d'un matériau sans présupposer d'équation constitutive est possible grâce à l'algorithme Data-Driven Identification développé par les auteurs. Il permet de mesurer les contraintes à partir des champs de déplacement et des forces appliquées à une structure donnée ; la particularité de la technique est l'absence d'équation constitutive sous-jacente. Dans le cas d'expériences réelles, l'algorithme a été appliqué avec succès sur une feuille d'élastomère perforée déformée sous une grande contrainte. Les déplacements sont recueillis par corrélation d'images numériques et les forces nettes à l'aide d'une cellule de charge. Cependant, ces données réelles sont incomplètes pour deux raisons : certaines valeurs de déplacement, près des bords ou dans une zone affectée par le bruit, sont manquantes et les informations sur les forces sont incomplètes par rapport aux exigences de l'algorithme DDI d'origine. La présente étude prouve qu'avec un traitement approprié des données, les champs de contrainte peuvent être identifiés de manière robuste. La solution repose sur la récupération des données manquantes de manière à ce qu'aucune hypothèse, à l'exception de l'équilibre de la quantité de mouvement linéaire, ne doive être faite. L'influence des paramètres d'entrée de la méthode est également discutée. L'étude globale est menée sur des données synthétiques : des données parfaites et incomplètes sont utilisées pour prouver la robustesse des solutions proposées. Par conséquent, le document peut être considéré comme un guide pratique pour la mise en œuvre de la méthode DDI