k-REWB matching cannot be solved in O(n to the 2k minus epsilon) time under SETH, is W[2]-hard parameterized by expression length, and 2-use 2-REWBs require superlinear time unless triangle detection does; 1-use REWBs admit an O(n log squared n) algorithm.
In: 24th EACSL Annual Conference on Computer Science Logic, LIPIcs
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
citation-role summary
background 2
other 1
citation-polarity summary
verdicts
UNVERDICTED 4representative citing papers
General criteria for minimal models of streaming transducers are established, yielding effective minimization for variants of streaming string-to-tree transducers that build terms at leaves or roots.
Epistemic realizability assigns verifier and generator programs to propositions and proves soundness and completeness for minimal, second-order, and higher-order intuitionistic logic.
Satisfiability of propositional logic with nonemptiness atom NE in team semantics is NP-complete, validity coNP-complete, and model checking polynomial-time.
citing papers explorer
-
On the Complexity of the Matching Problem of Regular Expressions with Backreferences
k-REWB matching cannot be solved in O(n to the 2k minus epsilon) time under SETH, is W[2]-hard parameterized by expression length, and 2-use 2-REWBs require superlinear time unless triangle detection does; 1-use REWBs admit an O(n log squared n) algorithm.
-
Minimization of Streaming Transducers
General criteria for minimal models of streaming transducers are established, yielding effective minimization for variants of streaming string-to-tree transducers that build terms at leaves or roots.
-
Verifiers and Generators: Epistemic Semantics for Intuitionistic Logic (Long Version)
Epistemic realizability assigns verifier and generator programs to propositions and proves soundness and completeness for minimal, second-order, and higher-order intuitionistic logic.
-
Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
Satisfiability of propositional logic with nonemptiness atom NE in team semantics is NP-complete, validity coNP-complete, and model checking polynomial-time.