Intersection non-emptiness and hardness within polynomial time

DOI10.1007/978-3-319-98654-8_23MaRDI QIDQ1622971zbMATH OpenOpenAlexFDO

Authors Mateus de Oliveira Oliveira, Michael Wehar

Publication date 22 November 2018

Full work available at URL https://doi.org/10.1007/978-3-319-98654-8_23

zbMATH Keywords

computational complexityintersection non-emptinessunary automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Hardness results for intersection non-emptiness
• On the complexity of intersecting regular, context-free, and tree languages
• The emptiness problem for intersections of regular languages
• The intersection problem for finite monoids
• Lengths of words accepted by nondeterministic finite automata

Cited in

(9)

• Two-dimensional pattern matching against local and regular-like picture languages
• On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
• Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices
• On the complexity of string matching for graphs
• Hardness results for intersection non-emptiness
• Recognizing picture languages by reductions to string languages
• scientific article; zbMATH DE number 7770055 (Why is no real title available?)
• Subset mapping problems in solvable automata
• Incremental algorithms for solving regular expression intersection non-emptiness

This page was built for publication: Intersection non-emptiness and hardness within polynomial time

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