6 citations · 7 across the 12 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
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.DS2017★ 1 cited
Topological Sorting under Regular Constraints
Antoine Amarilli, Charles Paperman
We introduce the constrained topological sorting problem (CTS): given a regular language K and a directed acyclic graph G with labeled vertices, determine if G has a topological so…
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…