Querying regular languages over sliding windows

DOI10.4230/LIPICS.FSTTCS.2016.18MaRDI QIDQ4636565zbMATH OpenOpenAlexFDO

Authors Moses Ganardi, Danny Hucke, Markus Lohrey

Publication date 19 April 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.FSTTCS.2016.18

zbMATH Keywords

regular languagesspace complexitystreaming algorithms

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Automata theory on sliding windows
• Randomized sliding window algorithms for regular languages
• Sliding windows over context-free languages
• Regular Programming for Quantitative Properties of Data Streams
• Sliding suffix tree

Cited in

(16)

• Dynamic data structures for timed automata acceptance
• Green's relations in deterministic finite automata
• Green's relations in finite transformation semigroups
• Automata theory on sliding windows
• Randomized sliding window algorithms for regular languages
• Sliding windows over context-free languages
• Visibly pushdown languages over sliding windows
• Derandomization for sliding window algorithms with strict correctness
• Longest Common Subsequence with Gap Constraints
• Subsequences in bounded ranges: matching and analysis problems
• Combinatorial algorithms for subsequence matching: a survey
• Longest common subsequence with gap constraints
• Regular languages in the sliding window model
• Dynamic membership for regular languages
• Property testing of regular languages with applications to streaming property testing of visibly pushdown languages
• Small space encoding and recognition of k-palindromic prefixes

This page was built for publication: Querying regular languages over sliding windows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636565)