Source author record

Andrey Mokhov

Andrey Mokhov appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Software Engineering Computational Complexity Logic in Computer Science Programming Languages

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

United Monoids: Finding Simplicial Sets and Labelled Algebraic Graphs in Trees

Graphs and various graph-like combinatorial structures, such as preorders and hypergraphs, are ubiquitous in programming. This paper focuses on representing graphs in a purely functional programming language like Haskell. There are several existing approaches; one of the most recently developed ones is the "algebraic graphs" approach (2017). It uses an algebraic data type to represent graphs and has attracted users, including from industry, due to its emphasis on equational reasoning and making a common class of bugs impossible by eliminating internal invariants. The previous formulation of algebraic graphs did not support edge labels, which was a serious practical limitation. In this paper, we redesign the main algebraic data type and remove this limitation. We follow a fairly standard approach of parameterising a data structure with a semiring of edge labels. The new formulation is both more general and simpler: the two operations for composing graphs used in the previous work can now be obtained from a single operation by fixing the semiring parameter to zero and one, respectively. By instantiating the new data type with different semirings, and working out laws for interpreting the resulting expression trees, we discover an unusual algebraic structure, which we call "united monoids", that is, a pair of monoids whose unit elements coincide. We believe that it is worth studying united monoids in their full generality, going beyond the graphs which prompted their discovery. To that end, we characterise united monoids with a minimal set of axioms, prove a few basic theorems, and discuss several notable examples. We validate the presented approach by implementing it in the open-source *algebraic-graphs* library. Our theoretical contributions are supported by proofs that are included in the paper and have also been machine-checked in Agda. By extending algebraic graphs with support for edge labels, we make them suitable for a much larger class of possible applications. By studying united monoids, we provide a theoretical foundation for further research in this area.

preprint2018arXiv

On the complexity of hazard-free circuits

The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards. These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions. As our main upper-bound result we show how to efficiently convert a Boolean circuit into a bounded-bit hazard-free circuit with only a polynomially large blow-up in the number of gates. Previously, the best known method yielded exponentially large circuits in the worst case, so our algorithm gives an exponential improvement. As a side result we establish the NP-completeness of several hazard detection problems.

preprint2016arXiv

An Empirical Comparison of Formalisms for Modelling and Analysis of Dynamic Reconfiguration of Dependable Systems

This paper uses a case study to evaluate empirically three formalisms of different kinds for their suitability for the modelling and analysis of dynamic reconfiguration of dependable systems. The requirements on an ideal formalism for dynamic software reconfiguration are defined. The reconfiguration of an office workflow for order processing is described, and the requirements on the reconfiguration of the workflow are defined. The workflow is modelled using the Vienna Development Method ($\mathrm{VDM}$), conditional partial order graphs ($\mathrm{CPOGs}$), and the basic Calculus of Communicating Systems for dynamic process reconfiguration (basic $\mathrm{CCS^{dp}}$), and verification of the reconfiguration requirements is attempted using the models. The formalisms are evaluated according to their ability to model the reconfiguration of the workflow, to verify the requirements on the workflow's reconfiguration, and to meet the requirements on an ideal formalism.

preprint2014arXiv

On Formalisms for Dynamic Reconfiguration of Dependable Systems

Three formalisms of different kinds - VDM, Maude, and basic CCSdp - are evaluated for their suitability for the modelling and verification of dynamic software reconfiguration using as a case study the dynamic reconfiguration of a simple office workflow for order processing. The research is ongoing, and initial results are reported.