Randomized sliding window algorithms for regular languages

DOI10.4230/LIPICS.ICALP.2018.127MaRDI QIDQ5002813zbMATH OpenFDO

Authors Moses Ganardi, Danny Hucke, Markus Lohrey

Publication date 28 July 2021

Full work available at URL https://arxiv.org/abs/1802.07600

zbMATH Keywords

randomized complexityregular languagessliding windows

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Recommendations

• Automata theory on sliding windows
• Querying regular languages over sliding windows
• Derandomization for sliding window algorithms with strict correctness
• Derandomization for sliding window algorithms with strict correctness
• Sliding windows over context-free languages

Cites work

• Approximate formulas for some functions of prime numbers
• Automata theory on sliding windows
• Communication Complexity
• Complete classifications for the communication complexity of regular languages
• Data streams. Models and algorithms.
• Edit Distance to Monotonicity in Sliding Windows
• Efficient Summing over Sliding Windows
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Maintaining Stream Statistics over Sliding Windows
• On randomized one-round communication complexity
• Probabilistic automata
• Querying regular languages over sliding windows

Cited in

(14)

• Automata theory on sliding windows
• Streaming algorithms for language recognition problems
• Querying regular languages over sliding windows
• Sliding windows over context-free languages
• Visibly pushdown languages over sliding windows
• Derandomization for sliding window algorithms with strict correctness
• Derandomization for sliding window algorithms with strict correctness
• Longest Common Subsequence with Gap Constraints
• Subsequences in bounded ranges: matching and analysis problems
• Pseudorandom generators for sliding-window algorithms
• Longest common subsequence with gap constraints
• Regular languages in the sliding window model
• 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: Randomized sliding window algorithms for regular languages

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