Sliding windows over context-free languages

DOI10.4230/LIPICS.MFCS.2018.15MaRDI QIDQ5005113zbMATH OpenFDO

Authors Moses Ganardi, Artur Jeż, Markus Lohrey

Publication date 4 August 2021

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2018.15

zbMATH Keywords

context-free languagessliding windowsstreaming algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Automata theory on sliding windows
• Querying regular languages over sliding windows
• Randomized sliding window algorithms for regular languages
• Streaming algorithms for language recognition problems
• On strongly context-free languages

Cites work

• Automata theory on sliding windows
• Data streams. Models and algorithms.
• Finite-Turn Pushdown Automata
• scientific article; zbMATH DE number 3876636 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Hyper-minimisation Made Efficient
• On Context-Free Languages
• Querying regular languages over sliding windows
• Visibly pushdown languages

Cited in

(10)

• Context-free languages can be accepted with absolutely no space overhead
• Automata theory on sliding windows
• Querying regular languages over sliding windows
• Randomized sliding window algorithms for regular languages
• Visibly pushdown languages over sliding windows
• Streamability of nested word transductions
• Derandomization for sliding window algorithms with strict correctness
• Pseudorandom generators for sliding-window algorithms
• Regular languages in the sliding window model
• Property testing of regular languages with applications to streaming property testing of visibly pushdown languages

This page was built for publication: Sliding windows over context-free languages

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