@inproceedings{62d54dc5895a402487ec58271953c9ca,

title = "Initial algebras and final coalgebras consisting of nondeterministic finite trace strategies",

abstract = "We study programs that perform I/O and finite nondeterministic choice, up to finite trace equivalence. For well-founded programs, we characterize which strategies (sets of traces) are definable, and axiomatize trace equivalence by means of commutativity between I/O and nondeterminism. This gives the set of strategies as an initial algebra for a polynomial endofunctor on semilattices. The strategies corresponding to non-well-founded programs constitute a final coalgebra for this functor. We also show corresponding results for countable nondeterminism.",

keywords = "final coalgebra, nondeterministic strategies, trace, algebraic effects, semilattices",

author = "Nathan Bowler and Levy, {Paul Blain} and Gordon Plotkin",

year = "2018",

month = dec,

day = "11",

doi = "10.1016/j.entcs.2018.11.003",

language = "English",

series = "Electronic Notes in Theoretical Computer Science",

pages = "23--44",

editor = "Sam Staton",

booktitle = "Proceedings of the 34th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV)",

note = "34th Conference on the Mathematical Foundations of Programming Semantics (MFPS 2018) ; Conference date: 06-06-2018 Through 09-06-2018",

}