Author name cluster

Sergey Goncharov

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2021 Journal Article

A metalanguage for guarded iteration

Sergey Goncharov
Christoph Rauch
Lutz Schröder

Notions of guardedness serve to delineate admissible recursive definitions in various settings in a compositional manner. In recent work, we have introduced an axiomatic notion of guardedness in symmetric monoidal categories, which serves as a unifying framework for various examples from program semantics, process algebra, and beyond. In the present paper, we propose a generic metalanguage for guarded iteration based on combining this notion with the fine-grain call-by-value paradigm, which we intend as a unifying programming language for guarded and unguarded iteration in the presence of computational effects. We give a generic (categorical) semantics of this language over a suitable class of strong monads supporting guarded iteration, and show it to be in touch with the standard operational behaviour of iteration by giving a concrete big-step operational semantics for a certain specific instance of the metalanguage and establishing soundness and (computational) adequacy for this case.

Details DOI

I&C Journal 2013 Journal Article

A coinductive calculus for asynchronous side-effecting processes

Sergey Goncharov
Lutz Schröder

We present an abstract framework for concurrent processes in which atomic steps have generic side effects, handled according to the principle of monadic encapsulation of effects. Processes in this framework are potentially infinite resumptions, modelled using final coalgebras over the monadic base. As a calculus for such processes, we introduce a concurrent extension of Moggiʼs monadic meta-language of effects. We establish soundness and completeness of a natural equational axiomatization of this calculus. Our main result is a corecursion scheme that is explicitly definable over the base language and provides flexible expressive means for the definition of new operators on processes, such as parallel composition. Moreover, we present initial results on verification methods for generic side-effecting processes.

Details DOI

TCS Journal 2011 Journal Article

Inductive inference and computable numberings

Klaus Ambos-Spies
Serikzhan Badaev
Sergey Goncharov

It has been previously observed that for many TxtEx -learnable computable families of computably enumerable (c. e. for short) sets all their computable numberings are evidently 0 ′ -equivalent, i. e. are equivalent with respect to reductions computable in the halting problem. We show that this holds for all TxtEx -learnable computable families of c. e. sets, and prove that, in general, the converse is not true. In fact there is a computable family A of c. e. sets such that all computable numberings of A are computably equivalent and A is not TxtEx -learnable. Moreover, we construct a computable family of c. e. sets which is not TxtBC -learnable though all of its computable numberings are 0 ′ -equivalent. We also give a natural example of a computable TxtBC -learnable family of c. e. sets which possesses non- 0 ′ -equivalent computable numberings. So, for the computable families of c. e. sets, the properties of TxtBC -learnability and 0 ′ -equivalence of all computable numberings are independent.

Details DOI