6 citations · 7 across the 12 of their papers we have counts for
Showing 2017 · cs.LOShow all
2 papers · 2 filters
cs.LO2017
Monadic Second-Order Logic with Arbitrary Monadic Predicates
Nathanaël Fijalkow, Charles Paperman
We study Monadic Second-Order Logic (MSO) over finite words, extended with (non-uniform arbitrary) monadic predicates. We show that it defines a class of languages that has algebra…
cs.LO2017
A Crevice on the Crane Beach: Finite-Degree Predicates
Michaël Cadilhac, Charles Paperman
First-order logic (FO) over words is shown to be equiexpressive with FO equipped with a restricted set of numerical predicates, namely the order, a binary predicate MSB, and th…