Automata Approaches for Palindromic Subsequence Problems
Explore palindromic subsequence automata and the longest common palindromic subsequence in computational mathematics, featuring efficient algorithms and a novel weighted finite automaton for solving the problem. The paper presents PSA construction and discusses the input alphabet and transition functions, highlighting time complexity analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Palindromic Subsequence Automata and Longest Common Palindromic Subsequence Md. Mahbubul Hasan, A. S. M. Sohidull Islam, M. Sohel Rahman, Ayon Sen Mathematics in Computer Science June 2017, Volume 11, Issue 2, pp 219 232 Presenter: Cheng-Han Wu Date:2017/12/26
Abstract In this paper, we present a novel weighted finite automaton called palindromic subsequence automaton(PSA) that is a compact representation of all the palindromic subsequences of a string. Then we use PSA to solve the longest common palindromic subsequence problem. Our automata based algorithms are efficient both in theory and in practice.
Longest Common Palindromic Subsequence ?1= ???? ?2= ???? ??? = ?,?,??,??? ???? = ???
Palindromic subsequence automata (PSA) String ?, reverse of ? be ?? PSA M accepts the first half of a palindromic subsequence of all palindromic subsequences of the given string S PSA M is a 6 tuple (?, ,?,?,?0,?)
PSA M ?:finite set of states. Here, ? is a subset of pairs of positions in ? and ?? ?0 ? is the initial state Each state ?? ? is associated with a pair of positions (??,??) where ??and ??refer to positions in ? and ??respectively and ?[??] = ??[??]
: is the input alphabet ?:? ? is a transition function ?:? ? ? assigns a edge cost between a pair of states 2,????< ? ??+ 1 1,????= ? ??+ 1 0,????> ? ??+ 1 ? ??,?,?? =
2,????< ? ??+ 1 1,????= ? ??+ 1 0,????> ? ??+ 1 ? ??,?,?? = ? ??= ??????? = ???????
PSA Construction NP(next position) is an array of size n SP(start position) is an array of size ? = ??????
? ??= ??????? ? = {a,b,c} = ??????? ?{(0,0)} ?{(1,1),(2,3),(4,2)} ?{ 2,3 , 4,2 ,(3,5)} ?{ 4,2 , 3,5 ,(4,4)} ?{ 3,5 , 4,4 ,(5,3)} ?{ 4,4 ,(5,3)} ?{(5,3)} ?{} time complexity:? ? + ? ?
Application of PSA: Computing an LCPS Step 1: Compute the PSA ?1of ?1 Step 2: Compute the PSA ?2of ?2 Step 3: Compute the CPSA ?3by intersecting ?1and ?2 Step 4: Compute the Max Length Automaton ?4of ?3
Time complexity ? ? + ?1? + ? + ?2? + ?1?2? ?1and ?2at most ?2, so worst case is ? ?4?
