1,721,102 research outputs found
On the structure of solution sets to regular word equations
Full text link© Joel D. Day and Florin Manea; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). For quadratic word equations, there exists an algorithm based on rewriting rules which generates a directed graph describing all solutions to the equation. For regular word equations - those for which each variable occurs at most once on each side of the equation - we investigate the properties of this graph, such as bounds on its diameter, size, and DAG-width, as well as providing some insights into symmetries in its structure. As a consequence, we obtain a combinatorial proof that the problem of deciding whether a regular word equation has a solution is in NP
Longest Gapped Repeats and Palindromes
No full textA gapped repeat (respectively, palindrome) occurring in a word is a
factor (respectively, ) of . In such a repeat (palindrome)
is called the arm of the repeat (respectively, palindrome), while is called
the gap. We show how to compute efficiently, for every position of the word
, the longest gapped repeat and palindrome occurring at that position,
provided that the length of the gap is subject to various types of
restrictions. That is, that for each position we compute the longest prefix
of such that (respectively, ) is a suffix of
(defining thus a gapped repeat -- respectively, palindrome
), and the length of is subject to the aforementioned restrictions
The Hardness of Solving Simple Word Equations
Full text linkWe investigate the class of regular-ordered word equations. In such equations, each variable occurs at most once in each side and the order of the variables occurring in both left and right hand sides is preserved (the variables can be, however, separated by potentially distinct constant factors). Surprisingly, we obtain that solving such simple equations, even when the sides contain exactly the same variables, is NP-hard. By considerations regarding the combinatorial structure of the minimal solutions of the more general quadratic equations we obtain that the satisfiability problem for regular-ordered equations is in NP. The complexity of solving such word equations under regular constraints is also settled. Finally, we show that a related class of simple word equations, that generalises one-variable equations, is in P
The CDSAT method for satisfiability modulo theories and assignments: an exposition
Full text linkMost SMT instances involve symbols from more than one theory. The equality sharing method for combining theory satisfiability procedures has been a standard for over forty years. For the Boolean part, the equality sharing method is interfaced with the CDCL procedure for SAT. CDCL guides the search by learning lemmas from conflicts between clauses and candidate model. In the standard integration of CDCL and equality sharing, the conflict-driven reasoning remains propositional, even if conflict-driven theory procedures exist. The MCSAT method integrates CDCL with a single conflict-driven theory procedure. The CDSAT method generalizes CDCL, MCSAT, and equality sharing, by allowing the integration of multiple (conflict-driven or not) theory procedures
Context insertions
No full textIn this paper we consider an operation of inserting contexts in a word controlled by a contextual scheme X which provides a selection criterion for contextual insertion. We say that a language L is k-stable w.r.t. a contextual scheme X if by making any k context insertions in a word of L we still obtain a word of L; L is k-anti-stable w.r.t. X if by making any k context insertions in a word of L we get a word not in L; L is called k-error-correctable w.r.t. X if by making any k context insertions in a word x of L we get either a word in L or a word not in L which cannot be also obtained by making k context insertions in a word z of L different from x. We prove that all these properties are decidable for regular languages. We then define a distance between two words that measures the minimal number of context insertions in one of the words in order to obtain the other. Some properties of this distance, which is actually a semimetric, are investigated. © 2011 Springer-Verlag Berlin Heidelberg
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
LIPIcs, Volume 216, CSL 2022, Complete Volume
No full textLIPIcs, Volume 216, CSL 2022, Complete Volum
Front Matter, Table of Contents, Preface, Conference Organization
No full textFront Matter, Table of Contents, Preface, Conference Organizatio
- …
