A new Boolean matrix representation for Catalan semirings
We construct a faithful representation of the semiring of all order-preserving decreasing transformations of a chain with $n+1$ elements by Boolean upper triangular $n\times n$-matrices.
Researcher profile
Mikhail Volkov
Mikhail Volkov contributes to research discovery and scholarly infrastructure.
ResearcherAffiliation not importedOpen to collaborate
Trust snapshot
Quick read
Trust 21 - EmergingVerification L1Unclaimed author
11works
0followers
10topics
4close collaborators
Actions
Decide how to stay connected
Identity and collaboration
How to connect with this researcher
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Open a focused conversation when the fit is right
Claim this author entity first to unlock direct invitations.
Research graph
See the researcher in context
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
Building this graph slice
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
11 published item(s)
preprint2022arXiv
Spatiotemporal attosecond control of electron pulses via subluminal terahertz waveforms
Shaping electron beams with the cycles of light provides femtosecond and attosecond time resolution in electron microscopy and enables fundamental quantum-coherent measurements. However, efficient light-electron control requires a prolonged interaction between the two beams for cascaded transfer of photon energy and momentum to the freely propagating electrons. Here we report the use of traveling evanescent terahertz waves to achieve velocity matching and thereby high acceleration gradients both in space and in time. With experiment and simulations, we demonstrate attosecond streaking, temporal pulse compression, acceleration and spatial focusing of sub-relativistic electron pulses with a single evanescent-wave element under the control of selected terahertz delays and phases. Based on these results, we propose to use a symmetric arrangement with two evanescent terahertz waves to generate isolated attosecond electron pulses in a beam with realistic parameters. These results establish subluminal terahertz waves as a promising tool for ultrafast electron pulse control.
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
Careful synchronization of partial deterministic finite automata
We approach the task of computing a carefully synchronizing word of optimum length for a given partial deterministic automaton, encoding the problem as an instance of SAT and invoking a SAT solver. Our experiments demonstrate that this approach gives satisfactory results for automata with up to 100 states even if very modest computational resources are used. We compare our results with the ones obtained by the first author for exact synchronization, which is another version of synchronization studied in the literature, and draw some theoretical conclusions.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Completely Reachable Automata
We present a few results and several open problems concerning complete deterministic finite automata in which every non-empty subset of the state set occurs as the image of the whole state set under the action of a suitable input word.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Dimensionality Reduction of Massive Sparse Datasets Using Coresets
In this paper we present a practical solution with performance guarantees to the problem of dimensionality reduction for very large scale sparse matrices. We show applications of our approach to computing the low rank approximation (reduced SVD) of such matrices. Our solution uses coresets, which is a subset of $O(k/\eps^2)$ scaled rows from the $n\times d$ input matrix, that approximates the sub of squared distances from its rows to every $k$-dimensional subspace in $\REAL^d$, up to a factor of $1\pm\eps$. An open theoretical problem has been whether we can compute such a coreset that is independent of the input matrix and also a weighted subset of its rows. %An open practical problem has been whether we can compute a non-trivial approximation to the reduced SVD of very large databases such as the Wikipedia document-term matrix in a reasonable time. We answer this question affirmatively. % and demonstrate an algorithm that efficiently computes a low rank approximation of the entire English Wikipedia. Our main technical result is a novel technique for deterministic coreset construction that is based on a reduction to the problem of $\ell_2$ approximation for item frequencies.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
A nonfinitely based semigroup of triangular matrices
A new sufficient condition under which a semigroup admits no finite identity basis has been recently suggested in a joint paper by Karl Auinger, Yuzhu Chen, Xun Hu, Yanfeng Luo, and the author (see http://arxiv.org/abs/1405.0783). Here we apply this condition to show the absence of a finite identity basis for the semigroup $\mathrm{UT}_3(\mathbb{R})$ of all upper triangular real $3\times 3$-matrices with 0s and/or 1s on the main diagonal. The result holds also for the case when $\mathrm{UT}_3(\mathbb{R})$ is considered as an involution semigroup under the reflection with respect to the secondary diagonal.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
The Finite Basis Problem for Kauffman Monoids
We prove a sufficient condition under which a semigroup admits no finite identity basis. As an application, it is shown that the identities of the Kauffman monoid $\mathcal{K}_n$ are nonfinitely based for each $n\ge 3$. This result holds also for the case when $\mathcal{K}_n$ is considered as an involution semigroup under either of its natural involutions.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
P(l)aying for Synchronization
Two topics are presented: synchronization games and synchronization costs. In a synchronization game on a deterministic finite automaton, there are two players, Alice and Bob, whose moves alternate. Alice wants to synchronize the given automaton, while Bob aims to make her task as hard as possible. We answer a few natural questions related to such games. Speaking about synchronization costs, we consider deterministic automata in which each transition has a certain price. The problem is whether or not a given automaton can be synchronized within a given budget. We determine the complexity of this problem. We also formulate a few open questions.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Matrix identities involving multiplication and transposition
We study matrix identities involving multiplication and unary operations such as transposition or Moore-Penrose inversion. We prove that in many cases such identities admit no finite basis.
0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv
The algebra of adjacency patterns: Rees matrix semigroups with reversion
We establish a surprisingly close relationship between universal Horn classes of directed graphs and varieties generated by so-called adjacency semigroups which are Rees matrix semigroups over the trivial group with the unary operation of reversion. In particular, the lattice of subvarieties of the variety generated by adjacency semigroups that are regular unary semigroups is essentially the same as the lattice of universal Horn classes of reflexive directed graphs. A number of examples follow, including a limit variety of regular unary semigroups and finite unary semigroups with NP-hard variety membership problems.
0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv
Representation Theory of Finite Semigroups, Semigroup Radicals and Formal Language Theory
In this paper we characterize the congruence associated to the direct sum of all irreducible representations of a finite semigroup over an arbitrary field, generalizing results of Rhodes for the field of complex numbers. Applications are given to obtain many new results, as well as easier proofs of several results in the literature, involving: triangularizability of finite semigroups; which semigroups have (split) basic semigroup algebras, two-sided semidirect product decompositions of finite monoids; unambiguous products of rational languages; products of rational languages with counter; and Černý's conjecture for an important class of automata.
0 citations0 reviewsNo code linkedOpen access