3 citations · 9 across the 7 of their papers we have counts for
8 papers
Disjunctive Complexity
Nikita Ivanov, Alexander Rubtsov, Michael Vyalyi
A recently introduced measure of Boolean functions complexity--disjunc\-tive complexity (DC)--is compared with other complexity measures: the space complexity of streaming algorith…
On universality of regular realizability problems
Alexander Rubtsov, Michael Vyalyi
We prove the universality of the regular realizability problems for several classes of filters. The filters are encodings of finite relations on the set of non-negative integers in…
The Simplest Proof of Parikh's Theorem via Derivation Trees
Alexander Rubtsov
Parikh's theorem is a fundamental result of the formal language's theory. There had been published many proofs and many papers claimed to provide a simplified proof, but most of th…
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems
Alexander Rubtsov, Mikhail Vyalyi
We consider general computational models: one-way and two-way finite automata, and logarithmic space Turing machines, all equipped with an auxiliary data structure (ADS). The defin…
On computational complexity of Set Automata
Alexander A. Rubtsov, Mikhail N. Vyalyi
We consider a computational model which is known as set automata. The set automata are one-way finite automata with an additional storage---the set. There are two kinds of set auto…
Regular realizability problems and context-free languages
Alexander A. Rubtsov, Mikhail N. Vyalyi
We investigate regular realizability (RR) problems, which are the problems of verifying whether intersection of a regular language -- the input of the problem -- and fixed language…
Regular realizability problems and regular languages
Alexander A. Rubtsov
We investigate regular realizability (RR) problems, which are the problems of verifying whether intersection of a regular language -- the input of the problem -- and fixed language…
Regular realizability problems and models of a generalized nondeterminism
A. Rubtsov, M. Vyalyi
Models of a generalized nondeterminism are defined by limitations on nonde- terministic behavior of a computing device. A regular realizability problem is a problem of verifying ex…