ﻻ يوجد ملخص باللغة العربية
We present polygraphic programs, a subclass of Albert Burronis polygraphs, as a computational model, showing how these objects can be seen as first-order functional programs. We prove that the model is Turing complete. We use polygraphic interpretations, a termination proof method introduced by the second author, to characterize polygraphic programs that compute in polynomial time. We conclude with a characterization of polynomial time functions and non-deterministic polynomial time functions.
We study idempotents in intensional Martin-Lof type theory, and in particular the question of when and whether they split. We show that in the presence of propositional truncation and Voevodskys univalence axiom, there exist idempotents that do not s
The elimination distance to some target graph property P is a general graph modification parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to graph properties expressible in first-order logic. We delimit the pro
Craig Squier proved that, if a monoid can be presented by a finite convergent string rewriting system, then it satisfies the homological finiteness condition left-FP3. Using this result, he constructed finitely presentable monoids with a decidable wo
There are different notions of computation, the most popular being monads, applicative functors, and arrows. In this article we show that these three notions can be seen as monoids in a monoidal category. We demonstrate that at this level of abstract
An {omega}-language is a set of infinite words over a finite alphabet X. We consider the class of recursive {omega}-languages, i.e. the class of {omega}-languages accepted by Turing machines with a Buchi acceptance condition, which is also the class