{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:38:49Z","timestamp":1740141529942,"version":"3.37.3"},"reference-count":55,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MI 717\/5-2","MI 717\/7-1","SCHR 1118\/8-2"],"award-info":[{"award-number":["MI 717\/5-2","MI 717\/7-1","SCHR 1118\/8-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Grant Agency of Czech Republic","award":["19-00902S"],"award-info":[{"award-number":["19-00902S"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,9,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>For every finitary monad $T$ on sets and every endofunctor $F$ on the category of $T$-algebras, we introduce the concept of an ffg-Elgot algebra for $F$, i.e. an algebra admitting coherent solutions for finite systems of recursive equations with effects represented by the monad $T$. The goal is to study the existence and construction of free ffg-Elgot algebras. To this end, we investigate the locally ffg fixed point $\\varphi F$, i.e. the colimit of all $F$-coalgebras with free finitely generated carrier, which is shown to be the initial ffg-Elgot algebra. This is the technical foundation for our main result: the category of ffg-Elgot algebras is monadic over the category of $T$-algebras.<\/jats:p>","DOI":"10.1093\/logcom\/exab049","type":"journal-article","created":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T11:11:47Z","timestamp":1626261107000},"page":"1429-1481","source":"Crossref","is-referenced-by-count":0,"title":["On the behaviour of coalgebras with side effects and algebras with effectful iteration"],"prefix":"10.1093","volume":"31","author":[{"given":"Ji\u0159\u00ed","family":"Ad\u00e1mek","sequence":"first","affiliation":[{"name":"Department of Mathematics, Faculty of Electrical Engineering, Czech Technical University in Prague, Trojanova 13, Praha 2, 120 01, Praha, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Milius","sequence":"additional","affiliation":[{"name":"Lehrstuhl f\u00fcr Theoretische Informatik, Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg, Martenstr. 3, 91058 Erlangen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henning","family":"Urbat","sequence":"additional","affiliation":[{"name":"Lehrstuhl f\u00fcr Theoretische Informatik, Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg, Martenstr. 3, 91058 Erlangen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,9,2]]},"reference":[{"key":"2021092001212626600_ref1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(02)00728-4","article-title":"Infinite trees and completely iterative theories: a coalgebraic view","volume":"300","author":"Aczel","year":"2003","journal-title":"Theoretical Computer Science"},{"key":"2021092001212626600_ref2","first-page":"1","article-title":"A coalgebraic view of infinite trees and iteration","volume-title":"Proceedings of Coalgebraic Methods in Computer Science (CMCS\u201901)","author":"Aczel","year":"2001"},{"key":"2021092001212626600_ref3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.jlamp.2017.11.003","article-title":"Fixed points of functors","volume":"95","author":"Ad\u00e1mek","year":"2018","journal-title":"Journal of Logical and Algebraic Methods in Programming"},{"key":"2021092001212626600_ref4","first-page":"1134","article-title":"On finitary functors. Theory and Applications of Categories","author":"Ad\u00e1mek","year":"2019"},{"key":"2021092001212626600_ref5","first-page":"144","article-title":"On algebras with effectful iteration","volume-title":"Proceedings of Coalgebraic Methods in Computer Science (CMCS\u201918)","author":"Ad\u00e1mek","year":"2018"},{"issue":"5:4","key":"2021092001212626600_ref6","first-page":"31","article-title":"Elgot algebras","volume":"2","author":"Ad\u00e1mek","year":"2006","journal-title":"Logical Methods in Computer Science"},{"key":"2021092001212626600_ref7","doi-asserted-by":"crossref","first-page":"1085","DOI":"10.1017\/S0960129506005706","article-title":"Iterative algebras at work","volume":"16","author":"Ad\u00e1mek","year":"2006","journal-title":"Mathematical Structures in Computer Science"},{"key":"2021092001212626600_ref8","doi-asserted-by":"crossref","first-page":"43","DOI":"10.2168\/LMCS-7(1:15)2011","article-title":"Semantics of higher-order recursion schemes","volume":"7","author":"Ad\u00e1mek","year":"2011","journal-title":"Logical Methods in Computer Science"},{"key":"2021092001212626600_ref9","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511600579","volume-title":"Locally Presentable and Accessible Categories","author":"Ad\u00e1mek","year":"1994"},{"key":"2021092001212626600_ref10","first-page":"251","article-title":"What are sifted colimits?","volume":"23","author":"Ad\u00e1mek","year":"2010","journal-title":"Theory and Applications of Categories"},{"volume-title":"Algebraic Theories","year":"2011","author":"Ad\u00e1mek","key":"2021092001212626600_ref11"},{"volume-title":"Acyclic Models and Resolvent Functors","year":"1965","author":"Applegate","key":"2021092001212626600_ref12"},{"key":"2021092001212626600_ref13","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01111838","article-title":"Coequalizers and free triples","volume":"116","author":"Barr","year":"1970","journal-title":"Mathematische Zeitschrift"},{"key":"2021092001212626600_ref14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-73235-5","volume-title":"Rational Series and Their Languages","author":"Berstel","year":"1988"},{"key":"2021092001212626600_ref15","article-title":"Iteration theories: the equational logic of iterative processes","volume-title":"EATCS Monographs on Theoretical Computer Science","author":"Bloom","year":"1993"},{"issue":"1:7","key":"2021092001212626600_ref16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2422085.2422092","article-title":"Sound and complete axiomatizations of coalgebraic language equivalence","volume":"14","author":"Bonsangue","year":"2013","journal-title":"ACM Transactions on Computational Logic"},{"volume-title":"Handbook of Categorical Algebra","year":"1994","author":"Borceux","key":"2021092001212626600_ref17"},{"key":"2021092001212626600_ref18","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(83)90059-2","article-title":"Fundamental properties of infinite trees","volume":"25","author":"Courcelle","year":"1983","journal-title":"Theoretical Computer Science"},{"key":"2021092001212626600_ref19","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/BF01187558","article-title":"Tensor products and entropic varieties","volume":"21","author":"Davey","year":"1985","journal-title":"Algebra Universalis"},{"key":"2021092001212626600_ref20","first-page":"1756","article-title":"Eilenberg\u2013Moore algebras for stochastic relations","volume-title":"Information and Computation","author":"Doberkat","year":"2006"},{"key":"2021092001212626600_ref21","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-01492-5","volume-title":"Handbook of Weighted automata","author":"Droste","year":"2009"},{"key":"2021092001212626600_ref22","first-page":"175","article-title":"Monadic computation and iterative algebraic theories","volume-title":"Logic Colloquium \u201873","author":"Elgot","year":"1975"},{"key":"2021092001212626600_ref23","first-page":"119","article-title":"Simulation vs. equivalence","volume-title":"Proceedings of 6th International Conference. Foundations of Computer Science","author":"\u00c9sik","year":"2010"},{"key":"2021092001212626600_ref24","first-page":"321","article-title":"Simulations of weighted tree automata","volume-title":"Proceedings of CIAA\u201911","author":"\u00c9sik","year":"2011"},{"key":"2021092001212626600_ref25","first-page":"193","article-title":"Abstract syntax and variable binding","volume-title":"Proceedings of LICS\u201999","author":"Fiore","year":"1999"},{"key":"2021092001212626600_ref26","doi-asserted-by":"crossref","first-page":"181","DOI":"10.24033\/bsmf.1777","article-title":"Sur divers produits de s\u00e9ries formelles","volume":"102","author":"Fliess","year":"1974","journal-title":"Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France"},{"key":"2021092001212626600_ref27","first-page":"1003","article-title":"R\u00e9dei\u2019s finiteness theorem for commutative semigroups","volume":"19","author":"Freyd","year":"1968","journal-title":"Proceedings of the American Mathematical Society"},{"key":"2021092001212626600_ref28","first-page":"128","article-title":"Algebras, coalgebras, monads and comonads","volume-title":"Proceedings of Coalgebraic Methods in Computer Science (CMCS\u201901)","author":"Ghani","year":"2001"},{"key":"2021092001212626600_ref29","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1017\/S0960129502003912","article-title":"Dualizing initial algebras","volume":"13","author":"Ghani","year":"2003","journal-title":"Mathematical Structures in Computer Science"},{"key":"2021092001212626600_ref30","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/0022-0000(79)90032-1","article-title":"Regular trees and the free iterative theory","volume":"18","author":"Ginali","year":"1979","journal-title":"Journal of Computer and System Sciences"},{"key":"2021092001212626600_ref31","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1112\/blms\/7.3.294","article-title":"Adjoint lifting theorems for categories of algebras","volume":"7","author":"Johnstone","year":"1975","journal-title":"Bulletin of the London Mathematical Society"},{"volume-title":"Topos Theory","year":"1977","author":"Johnstone","key":"2021092001212626600_ref32"},{"key":"2021092001212626600_ref33","first-page":"51","article-title":"Nominal coalgebraic data types with applications to lambda calculus","volume-title":"Logical Methods in Computer Science","author":"Kurz","year":"2013"},{"key":"2021092001212626600_ref34","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF01110627","article-title":"A fixpoint theorem for complete categories","volume":"103","author":"Lambek","year":"1968","journal-title":"Mathematische Zeitschrift"},{"key":"2021092001212626600_ref35","first-page":"637","article-title":"Autonomous equational categories","volume":"15","author":"Linton","year":"1966","journal-title":"Journal of Mathematics and Mechanics"},{"key":"2021092001212626600_ref36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2004.05.003","article-title":"Completely iterative algebras and completely iterative monads","volume":"196","author":"Milius","year":"2005","journal-title":"Information and Computation"},{"key":"2021092001212626600_ref37","first-page":"449","article-title":"A sound and complete calculus for finite stream circuits","volume-title":"Proceedings of LICS\u201910","author":"Milius","year":"2010"},{"issue":"3:22","key":"2021092001212626600_ref38","first-page":"32","article-title":"Proper functors and fixed points for finite behaviour","volume":"14","author":"Milius","year":"2018","journal-title":"Logical Methods in Computer Science"},{"key":"2021092001212626600_ref39","first-page":"107","article-title":"A new foundation for finitary corecursion: the locally finite fixpoint and its properties","volume-title":"Proceedings of FoSSaCS\u201916","author":"Milius","year":"2016"},{"article-title":"A new foundation for finitary corecursion and iterative algebras","author":"Milius","key":"2021092001212626600_ref40","doi-asserted-by":"crossref","DOI":"10.1016\/j.ic.2019.104456"},{"key":"2021092001212626600_ref42","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1007\/s10485-016-9457-8","article-title":"Regular behaviours with names: On rational fixpoints of endofunctors on nominal sets","volume":"24","author":"Milius","year":"2016","journal-title":"Applied Categorical Structures"},{"key":"2021092001212626600_ref43","first-page":"336","article-title":"Finitary corecursion for the infinitary lambda calculus","volume-title":"Proceedings of CALCO\u201915","author":"Milius"},{"key":"2021092001212626600_ref44","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/S0304-3975(00)00126-2","article-title":"Parametric corecursion","volume":"260","author":"Moss","year":"2001","journal-title":"Theoretical Computer Science"},{"key":"2021092001212626600_ref45","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0304-3975(83)90014-2","article-title":"Iterative algebras","volume":"25","author":"Nelson","year":"1983","journal-title":"Theoretical Computer Science"},{"key":"2021092001212626600_ref46","first-page":"280","article-title":"Towards a mathematical operational semantics","volume-title":"Proceedings of Logic in Computer Science (LICS\u201997)","author":"Plotkin","year":"1997"},{"volume-title":"The Theory of Finitely Generated Commutative Semigroups","year":"1965","author":"R\u00e9dei","key":"2021092001212626600_ref47"},{"key":"2021092001212626600_ref48","first-page":"22","article-title":"Rational streams coalgebraically","volume-title":"Logical Methods in Computer Science","author":"Rutten","year":"2008"},{"key":"2021092001212626600_ref49","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0019-9958(61)80020-X","article-title":"On the definition of a family of automata","volume":"4","author":"Sch\u00fctzenberger","year":"1961","journal-title":"Information and Control"},{"issue":"1:9","key":"2021092001212626600_ref50","first-page":"27","article-title":"Generalizing determinization from automata to coalgebras","volume":"9","author":"Silva","year":"2013","journal-title":"Logical Methods in Computer Science"},{"key":"2021092001212626600_ref51","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.entcs.2011.09.027","article-title":"Sound and complete axiomatization of trace semantics for probabilistic systems","volume":"276","author":"Silva","year":"2011","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"2021092001212626600_ref52","doi-asserted-by":"crossref","first-page":"3110","DOI":"10.1016\/j.jpaa.2014.10.005","article-title":"Congruences of convex algebras","volume":"219","author":"Sokolova","year":"2015","journal-title":"Journal of Pure and Applied Algebra"},{"key":"2021092001212626600_ref53","first-page":"331","article-title":"Proper semirings and proper convex functors","volume-title":"Proceedings of FoSSaCS 2018","author":"Sokolova","year":"2018"},{"key":"2021092001212626600_ref54","first-page":"229","article-title":"Unique fixed points vs. least fixed points","volume-title":"Theoretical Computer Science","author":"Tiuryn","year":"1980"},{"key":"2021092001212626600_ref55","first-page":"24:1","article-title":"Finite behaviours and finitary corecursion","volume-title":"Proceedings of CALCO\u201917","author":"Urbat","year":"2017"},{"key":"2021092001212626600_ref56","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1016\/j.jcss.2014.12.004","article-title":"Context-free coalgebras","volume":"81","author":"Winter","year":"2015","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/31\/6\/1429\/40407803\/exab049.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/31\/6\/1429\/40407803\/exab049.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T01:22:14Z","timestamp":1632100934000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/31\/6\/1429\/6358279"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":55,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,9,2]]},"published-print":{"date-parts":[[2021,9,3]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exab049","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"type":"print","value":"0955-792X"},{"type":"electronic","value":"1465-363X"}],"subject":[],"published-other":{"date-parts":[[2021,9]]},"published":{"date-parts":[[2021,9]]}}}