The Experts below are selected from a list of 60504 Experts worldwide ranked by ideXlab platform
Michel Rigo - One of the best experts on this subject based on the ideXlab platform.
-
Taking-and-merging games as rewrite games
Discrete Mathematics and Theoretical Computer Science, 2020Co-Authors: Eric Duchene, Victor Marsault, Aline Parreau, Michel RigoAbstract:This work is a contribution to the study of rewrite games. Positions are finite words, and the possible moves are defined by a finite number of local rewriting rules. We introduce and investigate taking-and-merging games, that is, where each rule is of the form a^k->epsilon. We give sufficient conditions for a game to be such that the losing positions (resp. the positions with a given Grundy value) form a Regular Language or a context-free Language. We formulate several related open questions in parallel with the famous conjecture of Guy about the periodicity of the Grundy function of octal games. Finally we show that more general rewrite games quickly lead to undecidable problems. Namely, it is undecidable whether there exists a winning position in a given Regular Language, even if we restrict to games where each move strictly reduces the length of the current position. We formulate several related open questions in parallel with the famous conjecture of Guy about the periodicity of the Grundy function of octal games.
-
Odometers on Regular Languages
Theory of Computing Systems, 2005Co-Authors: Valérie Berthé, Michel RigoAbstract:Odometers or "adding machines" are usually introduced in the context of positional numeration systems built on a strictly increasing sequence of integers. We generalize this notion to systems defined on an arbitrary infinite Regular Language. In this latter situation, if (A,
-
Construction of Regular Languages and recognizability of polynomials
Discrete Mathematics, 2002Co-Authors: Michel RigoAbstract:A generalization of numeration system in which N is recognizable by finite automata can be obtained by describing a lexicographically ordered infinite Regular Language. Here we show that if P ∈ Q[x] is a polynomial such that P(N) ⊂ N then we can construct a numeration system in which the set of representations of P(N) is Regular. The main issue in this construction is to setup a Regular Language with a density function equals to P(n + 1) − P(n) for n large enough.
-
numeration systems on a Regular Language arithmetic operations recognizability and formal power series
Theoretical Computer Science, 2001Co-Authors: Michel RigoAbstract:Abstract Generalizations of numeration systems in which N is recognizable by a finite automaton are obtained by describing a lexicographically ordered infinite Regular Language L⊂Σ ∗ . For these systems, we obtain a characterization of recognizable sets of integers in terms of N -rational formal series. After a study of the polynomial Regular Languages, we show that, if the complexity of L is Θ (n l ) (resp. if L is the complement of a polynomial Language), then multiplication by λ∈ N preserves recognizability only if λ=β l+1 (resp. if λ≠(#Σ) β ) for some β∈ N . Finally, we obtain sufficient conditions for the notions of recognizability for abstract systems and some positional number systems to be equivalent.
-
generalization of automatic sequences for numeration systems on a Regular Language
Theoretical Computer Science, 2000Co-Authors: Michel RigoAbstract:Let L be an infinite Regular Language on a totally ordered alphabet (Σ,<). Feeding a finite deterministic automaton (with output) with the words of L, enumerated lexicographically with respect to <, leads to an infinite sequence over the output alphabet of the automaton. This process generalizes the concept of k-automatic sequence for abstract numeration systems on a Regular Language (instead of systems in base k). Here, we study the first properties of these sequences and their relations with numeration systems.
Stavros Konstantinidis - One of the best experts on this subject based on the ideXlab platform.
-
an efficient algorithm for computing the edit distance of a Regular Language via input altering transducers
arXiv: Formal Languages and Automata Theory, 2014Co-Authors: Lila Kari, Stavros Konstantinidis, Steffen Kopecki, Meng YangAbstract:We revisit the problem of computing the edit distance of a Regular Language given via an NFA. This problem relates to the inherent maximal error-detecting capability of the Language in question. We present an efficient algorithm for solving this problem which executes in time $O(r^2n^2d)$, where $r$ is the cardinality of the alphabet involved, $n$ is the number of transitions in the given NFA, and $d$ is the computed edit distance. We have implemented the algorithm and present here performance tests. The correctness of the algorithm is based on the result (also presented here) that the particular error-detection property related to our problem can be defined via an input-altering transducer.
-
computing the edit distance of a Regular Language
Information & Computation, 2007Co-Authors: Stavros KonstantinidisAbstract:The edit distance (or Levenshtein distance) between two words is the smallest number of substitutions, insertions, and deletions of symbols that can be used to transform one of the words into the other. In this paper, we consider the problem of computing the edit distance of a Regular Language (the set of words accepted by a given finite automaton). This quantity is the smallest edit distance between any pair of distinct words of the Language. We show that the problem is of polynomial time complexity. In particular, for a given finite automaton A with n transitions, over an alphabet of r symbols, our algorithm operates in time O(n2r2q2( q+r)), where q is either the diameter of A (if A is deterministic), or the square of the number of states in A (if A is nondeterministic). Incidentally, we also obtain an upper bound on the edit distance of a Regular Language in terms of the automaton accepting the Language.
-
computing the levenshtein distance of a Regular Language
Information Theory Workshop, 2005Co-Authors: Stavros KonstantinidisAbstract:The edit distance (or Levenshtein distance) between two words is the smallest number of substitutions, insertions, and deletions of symbols that can be used to transform one of the words into the other. In this paper we consider the problem of computing the edit distance of a Regular Language (also known as constraint system), that is, the set of words accepted by a given finite automaton. This quantity is the smallest edit distance between any pair of distinct words of the Language. We show that the problem is of polynomial time complexity. We distinguish two cases depending on whether the given automaton is deterministic or nondeterministic. In the latter case the time complexity is higher.
-
ITW - Computing the Levenshtein distance of a Regular Language
IEEE Information Theory Workshop 2005., 2005Co-Authors: Stavros KonstantinidisAbstract:The edit distance (or Levenshtein distance) between two words is the smallest number of substitutions, insertions, and deletions of symbols that can be used to transform one of the words into the other. In this paper we consider the problem of computing the edit distance of a Regular Language (also known as constraint system), that is, the set of words accepted by a given finite automaton. This quantity is the smallest edit distance between any pair of distinct words of the Language. We show that the problem is of polynomial time complexity. We distinguish two cases depending on whether the given automaton is deterministic or nondeterministic. In the latter case the time complexity is higher.
Michal Zivukelson - One of the best experts on this subject based on the ideXlab platform.
-
Regular Language constrained sequence alignment revisited
Journal of Computational Biology, 2011Co-Authors: Gregory Kucherov, Tamar Pinhas, Michal ZivukelsonAbstract:Imposing constraints in the form of a finite automaton or a Regular expression is an effective way to incorporate additional a priori knowledge into sequence alignment procedures. With this motivation, the Regular Expression Constrained Sequence Alignment Problem was introduced, which proposed an O(n^2t^4) time and O(n^2t^2) space algorithm for solving it, where n is the length of the input strings and t is the number of states in the input non-deterministic automaton. A faster O(n^2t^3) time algorithm for the same problem was subsequently proposed. In this article, we further speed up the algorithms for Regular Language Constrained Sequence Alignment by reducing their worst case time complexity bound to O(n^2t^3/log t). This is done by establishing an optimal bound on the size of Straight-Line Programs solving the maxima computation subproblem of the basic dynamic programming algorithm. We also study another solution based on a Steiner Tree computation. While it does not improve worst case, our simulations show that both approaches are efficient in practice, especially when the input automata are dense.
-
Regular Language constrained sequence alignment revisited
International Workshop on Combinatorial Algorithms, 2010Co-Authors: Gregory Kucherov, Tamar Pinhas, Michal ZivukelsonAbstract:Imposing constraints in the form of a finite automaton or a Regular expression is an effective way to incorporate additional a priori knowledge into sequence alignment procedures. With this motivation, Arslan [1] introduced the Regular Language Constrained Sequence Alignment Problem and proposed an O(n2t4) time and O(n2t2 space algorithm for solving it, where n is the length of the input strings and t is the number of states in the non-deterministic automaton, which is given as input. Chung et al. [2] proposed a faster O(n2t3) time algorithm for the same problem. In this paper, we further speed up the algorithms for Regular Language Constrained Sequence Alignment by reducing their worst case time complexity bound to O(n2t3/ log t). This is done by establishing an optimal bound on the size of Straight-Line Programs solving the maxima computation subproblem of the basic dynamic programming algorithm. We also study another solution based on a Steiner Tree computation. While it does not improve the run time complexity in the worst case, our simulations show that both approaches are efficient in practice, especially when the input automata are dense.
Kai Salomaa - One of the best experts on this subject based on the ideXlab platform.
-
Pseudoknot-generating operation
Theoretical Computer Science, 2017Co-Authors: Da Jung Cho, Yo-sub Han, Kai SalomaaAbstract:Abstract A pseudoknot is a crucial intra-molecular structure formed primarily in RNA strands and closely related to important biological processes. This motivates us to define an operation that generates all pseudoknots from a given sequence and consider algorithmic and Language theoretic properties of the operation. We design an efficient algorithm that decides whether or not a given string is a pseudoknot of a Regular Language L . Our algorithm runs in linear time if L is given by a deterministic finite automaton. We study closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms that check whether or not a Regular Language L contains a pseudoknot or a pseudoknot generated by some string of L . Furthermore, we show that the corresponding questions for context-free Languages are undecidable.
-
SOFSEM - Pseudoknot-Generating Operation
Lecture Notes in Computer Science, 2016Co-Authors: Da Jung Cho, Yo-sub Han, Kai SalomaaAbstract:A pseudoknot is an intra-molecular structure formed primarily in RNA strands and much research has been done to predict efficiently pseudoknot structures in RNA. We define an operation that generates all pseudoknots from a given sequence and consider algorithmic and Language theoretic properties of the operation. We give an efficient algorithm to decide whether a given string is a pseudoknot of a Regular Language L--the runtime is linear if L is given by a deterministic finite automaton. We consider closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms to decide whether a Regular Language L contains a pseudoknot or a pseudoknot generated by some string of L. Furthermore, we show that the corresponding questions for context-free Languages are undecidable.
-
the edit distance between a Regular Language and a context free Language
International Journal of Foundations of Computer Science, 2013Co-Authors: Yo-sub Han, K O Sangki, Kai SalomaaAbstract:The edit-distance between two strings is the smallest number of operations required to transform one string into the other. The distance between Languages L1 and L2 is the smallest edit-distance be...
-
computing the edit distance between a Regular Language and a context free Language
Developments in Language Theory, 2012Co-Authors: Yo-sub Han, Kai SalomaaAbstract:The edit-distance between two strings is the smallest number of operations required to transform one string into the other. The edit-distance problem for two Languages is to find a pair of strings, each of which is from different Language, with the minimum edit-distance. We consider the edit-distance problem for a Regular Language and a context-free Language and present an efficient algorithm that finds an optimal alignment of two strings, each of which is from different Language. Moreover, we design a faster algorithm for the edit-distance problem that only finds the minimum number of operations of the optimal alignment.
-
Intercode Regular Languages
Fundamenta Informaticae, 2007Co-Authors: Yo-sub Han, Kai Salomaa, Derick WoodAbstract:Intercodes are a generalization of comma-free codes. Using the structural properties of finite-state automata recognizing an intercode we develop a polynomial-time algorithm for determining whether or not a given Regular Language L is an intercode. If the answer is yes, our algorithm yields also the smallest index k such that L is a k-intercode. Furthermore, we examine the prime intercode decomposition of intercode Regular Languages and design an algorithm for the intercode primality test of an intercode recognized by a finite-state automaton. We also propose an algorithm that computes the prime intercode decomposition of an intercode Regular Language in polynomial time. Finally, we demonstrate that the prime intercode decomposition need not be unique.
Gregory Kucherov - One of the best experts on this subject based on the ideXlab platform.
-
Regular Language constrained sequence alignment revisited
Journal of Computational Biology, 2011Co-Authors: Gregory Kucherov, Tamar Pinhas, Michal ZivukelsonAbstract:Imposing constraints in the form of a finite automaton or a Regular expression is an effective way to incorporate additional a priori knowledge into sequence alignment procedures. With this motivation, the Regular Expression Constrained Sequence Alignment Problem was introduced, which proposed an O(n^2t^4) time and O(n^2t^2) space algorithm for solving it, where n is the length of the input strings and t is the number of states in the input non-deterministic automaton. A faster O(n^2t^3) time algorithm for the same problem was subsequently proposed. In this article, we further speed up the algorithms for Regular Language Constrained Sequence Alignment by reducing their worst case time complexity bound to O(n^2t^3/log t). This is done by establishing an optimal bound on the size of Straight-Line Programs solving the maxima computation subproblem of the basic dynamic programming algorithm. We also study another solution based on a Steiner Tree computation. While it does not improve worst case, our simulations show that both approaches are efficient in practice, especially when the input automata are dense.
-
Regular Language constrained sequence alignment revisited
International Workshop on Combinatorial Algorithms, 2010Co-Authors: Gregory Kucherov, Tamar Pinhas, Michal ZivukelsonAbstract:Imposing constraints in the form of a finite automaton or a Regular expression is an effective way to incorporate additional a priori knowledge into sequence alignment procedures. With this motivation, Arslan [1] introduced the Regular Language Constrained Sequence Alignment Problem and proposed an O(n2t4) time and O(n2t2 space algorithm for solving it, where n is the length of the input strings and t is the number of states in the non-deterministic automaton, which is given as input. Chung et al. [2] proposed a faster O(n2t3) time algorithm for the same problem. In this paper, we further speed up the algorithms for Regular Language Constrained Sequence Alignment by reducing their worst case time complexity bound to O(n2t3/ log t). This is done by establishing an optimal bound on the size of Straight-Line Programs solving the maxima computation subproblem of the basic dynamic programming algorithm. We also study another solution based on a Steiner Tree computation. While it does not improve the run time complexity in the worst case, our simulations show that both approaches are efficient in practice, especially when the input automata are dense.
