Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices

DOI10.1007/978-3-030-48516-0_20OpenAlexW3031538300MaRDI QIDQ5041266

Daniel Průša, Michael Wehar

Publication date: 13 October 2022

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-48516-0_20

zbMATH Keywords

Boolean matrixfast matrix multiplicationtwo-dimensional pattern matchingsubmatriceslocal picture languagetriangle finding-hard problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On minimum witnesses for Boolean matrix multiplication
• The maximum edge biclique problem is NP-complete
• Intersection non-emptiness and hardness within polynomial time
• Two-dimensional pattern matching against basic picture languages
• Lengths of words accepted by nondeterministic finite automata
• Fast context-free grammar parsing requires fast boolean matrix multiplication
• Finding a Minimum Circuit in a Graph
• If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Multiplying matrices faster than coppersmith-winograd

This page was built for publication: Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices