Transducing Markov Sequences

Summary: Studies Markov-sequence queries via finite-state transducers: computing answer probabilities and top-k/ordered enumeration. Shows sub-exponential-approximate enumeration is intractable (even for fixed transducers), gives a matching heuristic, and isolates tractable regex-like extractor subclasses. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1503
Venue: PODS
Year: 2010
Pagerank: 4.1945683e-05
Overall Rank: 12,213 | 15.04%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Benny Kimelfeld
2. Christopher Ré

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,323	Optimizing and Parallelizing Ranked Enumeration	2011	VLDB	5.5693009e-05
8,378	Probabilistic Management of OCR Data using an RDBMS	2012	VLDB	4.5320288e-05
9,423	Database Principles in Information Extraction	2014	PODS	4.3441378e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
149	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00041101118
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
467	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00022443768
477	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00022221803
706	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017845469
1,073	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00014264992
1,123	A Transducer-Based XML Query Processor	2002	VLDB	0.00013849322
1,268	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012931993
1,970	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.896375e-05
2,875	MayBMS: A Probabilistic Database Management System	2009	SIGMOD	7.9742313e-05
3,398	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.141911e-05
3,929	Maximally Joining Probabilistic Data	2007	PODS	6.6248763e-05
4,442	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.186154e-05
5,296	Running Tree Automata on Probabilistic XML	2009	PODS	5.5802694e-05
5,759	Indexing Correlated Probabilistic Databases	2009	SIGMOD	5.3392211e-05
6,681	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	4.9643102e-05
6,838	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	4.9109732e-05
13,547	Lahar Demonstration: Warehousing Markovian Streams	2009	VLDB	-

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
6,284	Probabilistic XML via Markov Chains	2010	VLDB	5.128131e-05
3,251	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS	7.3215694e-05
12,042	E-Matching: Event Processing over Noisy Sequences in Real Time	2013	SIGMOD	4.1945683e-05
5,796	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.3240234e-05
4,064	Similarity-Based Queries	1995	PODS	6.4820797e-05
9,358	Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories	2014	VLDB	4.3510473e-05
2,293	Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation	2019	PODS	9.0899933e-05
8,143	Approximate Substring Matching over Uncertain Strings	2011	VLDB	4.5768015e-05
8,306	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5435639e-05