Initial algebras and final coalgebras consisting of nondeterministic finite trace strategies

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Standard

Initial algebras and final coalgebras consisting of nondeterministic finite trace strategies. / Bowler, Nathan; Levy, Paul Blain; Plotkin, Gordon.

Proceedings of the 34th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV). ed. / Sam Staton. 2018. p. 23-44 (Electronic Notes in Theoretical Computer Science; Vol. 341).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Bowler, N, Levy, PB & Plotkin, G 2018, Initial algebras and final coalgebras consisting of nondeterministic finite trace strategies. in S Staton (ed.), Proceedings of the 34th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV). Electronic Notes in Theoretical Computer Science, vol. 341, pp. 23-44, 34th Conference on the Mathematical Foundations of Programming Semantics (MFPS 2018), Halifax, Canada, 6/06/18. https://doi.org/10.1016/j.entcs.2018.11.003

APA

Bowler, N., Levy, P. B., & Plotkin, G. (2018). Initial algebras and final coalgebras consisting of nondeterministic finite trace strategies. In S. Staton (Ed.), Proceedings of the 34th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV) (pp. 23-44). (Electronic Notes in Theoretical Computer Science; Vol. 341). https://doi.org/10.1016/j.entcs.2018.11.003

Vancouver

Bowler N, Levy PB, Plotkin G. Initial algebras and final coalgebras consisting of nondeterministic finite trace strategies. In Staton S, editor, Proceedings of the 34th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV). 2018. p. 23-44. (Electronic Notes in Theoretical Computer Science). https://doi.org/10.1016/j.entcs.2018.11.003

Author

Bowler, Nathan ; Levy, Paul Blain ; Plotkin, Gordon. / Initial algebras and final coalgebras consisting of nondeterministic finite trace strategies. Proceedings of the 34th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV). editor / Sam Staton. 2018. pp. 23-44 (Electronic Notes in Theoretical Computer Science).

Bibtex

@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",

}

RIS

TY - GEN

T1 - Initial algebras and final coalgebras consisting of nondeterministic finite trace strategies

AU - Bowler, Nathan

AU - Levy, Paul Blain

AU - Plotkin, Gordon

PY - 2018/12/11

Y1 - 2018/12/11

N2 - 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.

AB - 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.

KW - final coalgebra

KW - nondeterministic strategies

KW - trace

KW - algebraic effects

KW - semilattices

U2 - 10.1016/j.entcs.2018.11.003

DO - 10.1016/j.entcs.2018.11.003

M3 - Conference contribution

T3 - Electronic Notes in Theoretical Computer Science

SP - 23

EP - 44

BT - Proceedings of the 34th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV)

A2 - Staton, Sam

T2 - 34th Conference on the Mathematical Foundations of Programming Semantics (MFPS 2018)

Y2 - 6 June 2018 through 9 June 2018

ER -