Showing cs.LOShow all
2 papers · 1 filter
cs.LO2023
The Complexity of Satisfiability Checking for Symbolic Finite Automata
Rodrigo Raya
We study the satisfiability problem of symbolic finite automata and decompose it into the satisfiability problem of the theory of the input characters and the monadic second-order…
cs.LO2021
NP Satisfiability for Arrays as Powers
Rodrigo Raya, Viktor Kunčak
We show that the satisfiability problem for the quantifier-free theory of product structures with the equicardinality relation is in NP. As an application, we extend the combinator…