Browsing CAS: Computer Science: Technical Reports by Author "Wymann-Böni, M."

Now showing items 1-2 of 2

A Characterization of First-Order Definable Subsets on Classes of Finite Total Orders

Kfoury, A.J.; Wymann-Böni, M. (Boston University Computer Science Department, 1993-08)

We give an explicit and easy-to-verify characterization for subsets in finite total orders (infinitely many of them in general) to be uniformly definable by a first-order formula. From this characterization we derive ...
Fixed Point vs. First-Order Logic on Finite Ordered Structures with Unary Relations

Kfoury, A.J.; Wymann-Böni, M. (Boston University Computer Science Department, 1993-08-11)

We prove that first order logic is strictly weaker than fixed point logic over every infinite classes of finite ordered structures with unary relations: Over these classes there is always an inductive unary relation which ...

Now showing items 1-2 of 2

Search OpenBU