On equivalence of two tests for codes.
On existentially first-order definable languages and their relation to NP
On Existentially First-Order Definable Languages and Their Relation to NP
Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language L: the unbalanced polynomial-time leaf language class determined by L equals iff L is existentially but not quantifierfree definable in FO[<, min, max, +1, −1]. Furthermore, no such class lies properly between NP and co-1-NP or NP⊕co-NP. The proofs rely on a result of Pin and Weil characterizing the automata of existentially first-order definable languages.
On extremum-searching approximate probabilistic algorithms
On families recognizable by finite branching automata
On free inverse monoid languages
On free Turing algebras
On frontiers of regular trees
On -machines generating intersection and union of generable languages
On generating all solutions of generalized satisfiability problems
On geometric automata which can nondeterministically choose auxiliary points
On global induction mechanisms in a -calculus with explicit approximations
We investigate a Gentzen-style proof system for the first-order -calculus based on cyclic proofs, produced by unfolding fixed point formulas and detecting repeated proof goals. Our system uses explicit ordinal variables and approximations to support a simple semantic induction discharge condition which ensures the well-foundedness of inductive reasoning. As the main result of this paper we propose a new syntactic discharge condition based on traces and establish its equivalence with the semantic...
On global induction mechanisms in a μ-calculus with explicit approximations
We investigate a Gentzen-style proof system for the first-order μ-calculus based on cyclic proofs, produced by unfolding fixed point formulas and detecting repeated proof goals. Our system uses explicit ordinal variables and approximations to support a simple semantic induction discharge condition which ensures the well-foundedness of inductive reasoning. As the main result of this paper we propose a new syntactic discharge condition based on traces and establish its equivalence with the semantic...
On graph products of automatic monoids
The graph product is an operator mixing direct and free products. It is already known that free products and direct products of automatic monoids are automatic. The main aim of this paper is to prove that graph products of automatic monoids of finite geometric type are still automatic. A similar result for prefix-automatic monoids is established.
On graph products of automatic monoids
The graph product is an operator mixing direct and free products. It is already known that free products and direct products of automatic monoids are automatic. The main aim of this paper is to prove that graph products of automatic monoids of finite geometric type are still automatic. A similar result for prefix-automatic monoids is established.
On hardly linearly provable systems
A well-known theorem of Rabin yields a dimensional lower bound on the width of complete polynomial proofs of a system of linear algebraic inequalities. In this note we investigate a practically motivated class of systems where the same lower bound can be obtained on the width of almost all (noncomplete) linear proofs. The proof of our result is based on the Helly Theorem.
On hierarchy of the positioned eco-grammar systems
Positioned eco-grammar systems (PEG systems, for short) were introduced in our previous papers. In this paper we engage in a new field of research, the hierarchy of PEG systems, namely in the hierarchy of the PEG systems according to the number of agents presented in the environment and according to the number of types of agents in the system.
On infinitary finite length codes
On infinite real trace rational languages of maximum topological complexity.
On k-Sets in Arrangements of Curves and Surfaces.