Transducing Markov sequences
DOI10.1145/2630065zbMATH Open1321.68368OpenAlexW2165831358MaRDI QIDQ5501935FDOQ5501935
Authors: Benny Kimelfeld, Christopher Re 
Publication date: 14 August 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2630065
Recommendations
- Querying sequence databases with transducers
- Sequences, datalog, and transducers
- Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source
- Moments of the count of a regular expression in a heterogeneous random sequence
- scientific article; zbMATH DE number 1773097
hidden Markov modelsenumerationtransducersprobabilistic databasesMarkov sequencesranked query evaluation
Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Data structures (68P05) Database theory (68P15)
Cites Work
- Biological Sequence Analysis
- Finding the k Shortest Paths
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- The complexity of computing the permanent
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
- Finding the K Shortest Loopless Paths in a Network
- On generating all maximal independent sets
- Factor graphs and the sum-product algorithm
- Title not available (Why is that?)
- State complexity of some operations on binary regular languages
- Optimal aggregation algorithms for middleware.
- On the complexity of database queries
- Title not available (Why is that?)
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Probabilistic quantifiers and games
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Learning information extraction rules for semi-structured and free text
- Sequences, datalog, and transducers
- Querying sequence databases with transducers
Cited In (1)
Uses Software
This page was built for publication: Transducing Markov sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501935)
