Two-dimensional pattern matching against local and regular-like picture languages
From MaRDI portal
Publication:2029490
DOI10.1016/j.tcs.2020.12.026zbMath1504.68109OpenAlexW3113919547MaRDI QIDQ2029490
František Mráz, Michael Wehar, Daniel Průša
Publication date: 3 June 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.12.026
picture languagetwo-dimensional pattern matchinglocal picture languagetriangle-finding problemtwo-dimensional finite automaton
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors
- Fast two-dimensional pattern matching
- Some properties of two-dimensional on-line tessellation acceptors
- Intersection non-emptiness and hardness within polynomial time
- Simple picture processing based on finite automata and regular grammars
- Two-dimensional pattern matching against basic picture languages
- Decision problems for restricted variants of two-dimensional automata
- Lengths of words accepted by nondeterministic finite automata
- New operations and regular expressions for two-dimensional languages over one-letter alphabet
- Strategies to scan pictures with automata based on Wang tiles
- Fast context-free grammar parsing requires fast boolean matrix multiplication
- Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages
- Efficient randomized pattern-matching algorithms
- Finding Even Cycles Even Faster
- Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices
- Template-Based Pattern Matching in Two-Dimensional Arrays
- Two-dimensional Sgraffito automata
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Multiplying matrices faster than coppersmith-winograd
