Deterministic Regular Expressions in Linear Time

Summary: Linear-time O(|e|) algorithm to test whether a regular expression e is deterministic, improving the prior O(σ|e|) Glushkov-based bound via a novel structural decomposition of e's parse tree. Combined matching in O(|e|+|w|) for star-free, bounded-occurrence, and bounded plus-depth deterministic REs, and O(|e|+|w| log log |e|) for arbitrary deterministic REs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1563
Venue: PODS
Year: 2012
Pagerank: 5.093636e-05
Overall Rank: 12,299 | 15.62%
DOI: 10.1145/2213556.2213566

Incoming Non-self Citations Over Time

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

Authors

1. Benoît Groz (INRIA; University of Lille)
2. Sebastian Maneth (National ICT Australia; University of New South Wales)
3. Sławek Staworko (INRIA; University of Lille)

BibTeX Citation

@inproceedings{groz_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Deterministic Regular Expressions in Linear Time}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213566},
        doi = {10.1145/2213556.2213566},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Groz, Benoît and Maneth, Sebastian and Staworko, Sławek},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,758	Validating Streaming XML Documents	2002	PODS	9.8162828e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS
2	341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB
3	1,658	Finding Regular Simple Paths in Graph Databases	1989	VLDB
4	12,625	The Complexity of Reasoning about Pattern-based XML Schemas	2007	PODS
5	12,365	The Complexity of Text-Preserving XML Transformations	2011	PODS
6	13,683	Efficient Evaluation for a Temporal Logic on Changing XML Documents	2011	PODS
7	2,619	Constant Delay Algorithms for Regular Document Spanners	2018	PODS
8	10,163	Optimal Enumeration of Regular Pattern Matches	2026	PODS
9	5,346	Running Tree Automata on Probabilistic XML	2009	PODS
10	4,391	Scalable Regular Expression Matching on Data Streams	2008	SIGMOD