Two-dimensional pattern matching against local and regular-like picture languages

DOI10.1016/J.TCS.2020.12.026MaRDI QIDQ2029490zbMATH OpenOpenAlexFDO

Authors František Mráz, Daniel Průša, Michael Wehar

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

zbMATH Keywords

local picture languagepicture languagetriangle-finding problemtwo-dimensional finite automatontwo-dimensional pattern matching

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Two-dimensional pattern matching against basic picture languages
• Template-based pattern matching in two-dimensional arrays
• On two-dimensional pattern-matching languages and their decision problems
• Complexity of sets of two-dimensional patterns
• Complexity of matching sets of two-dimensional patterns by two-dimensional on-line tessellation automaton

Cites work

• Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices
• Decision problems for restricted variants of two-dimensional automata
• Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages
• Deterministic recognizability of picture languages with Wang automata
• Efficient randomized pattern-matching algorithms
• Fast context-free grammar parsing requires fast Boolean matrix multiplication
• Fast two-dimensional pattern matching
• Finding Even Cycles Even Faster
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• scientific article; zbMATH DE number 5968943 (Why is no real title available?)
• scientific article; zbMATH DE number 1003305 (Why is no real title available?)
• scientific article; zbMATH DE number 3937199 (Why is no real title available?)
• scientific article; zbMATH DE number 605806 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Intersection non-emptiness and hardness within polynomial time
• Lengths of words accepted by nondeterministic finite automata
• Multiplying matrices faster than coppersmith-winograd
• New operations and regular expressions for two-dimensional languages over one-letter alphabet
• Simple picture processing based on finite automata and regular grammars
• Some properties of two-dimensional on-line tessellation acceptors
• Strategies to scan pictures with automata based on Wang tiles
• Template-based pattern matching in two-dimensional arrays
• Two-dimensional pattern matching against basic picture languages
• Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors
• Two-dimensional Sgraffito automata

Cited in

(10)

• On two-dimensional pattern-matching languages and their decision problems
• Two-dimensional pattern matching against basic picture languages
• Complexity of sets of two-dimensional patterns
• Complexity of matching sets of two-dimensional patterns by two-dimensional on-line tessellation automaton
• On contour representation of two dimensional patterns
• Pattern-matching problems for 2-dimensional images described by finite automata
• Template-based pattern matching in two-dimensional arrays
• Implementation and Application of Automata
• Implementation and Application of Automata
• The four corners problem over larger alphabets

This page was built for publication: Two-dimensional pattern matching against local and regular-like picture languages

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