Search results for "Computer Science::Formal Languages and Automata Theory"
showing 10 items of 228 documents
On Horn spectra
1991
Abstract A Horn spectrum is a spectrum of a Horn sentence. We show that to solve Asser's problem, and consequently the EXPTIME = ? NEXPTIME question it suffices to consider the class of Horn spectra. We also pose the problem whether or not the generator of every Horn spectrum is a spectrum. We prove that from a negative solution of the generator problem, a negative answer for the EXPTIME = ? NEXPTIME question follows. Some other relations between the generator problem and Asser's problem are given. Finally, the relativized version of the generator problem is formulated and it is shown that it has an affirmative solution for some oracles, and a negative solution for some others.
Balance Properties and Distribution of Squares in Circular Words
2008
We study balance properties of circular words over alphabets of size greater than two. We give some new characterizations of balanced words connected to the Kawasaki-Ising model and to the notion of derivative of a word. Moreover we consider two different generalizations of the notion of balance, and we find some relations between them. Some of our results can be generalised to non periodic infinite words as well.
Hamming, Permutations and Automata
2007
Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A.Ambainis and R.Freivalds that quantum finite automata with pure states can have exponentially smaller number of states than deterministic finite automata recognizing the same language. There was a never published "folk theorem" proving that quantum finite automata with mixed states are no more than superexponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We prove that there is an infinite sequence of distinct int…
Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States
2008
Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A.Ambainis and R.Freivalds that quantum finite automata with pure states can have exponentially smaller number of states than deterministic finite automata recognizing the same language. There was a never published "folk theorem" proving that quantum finite automata with mixed states are no more than super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We use a novel proof technique based on Kolmogorov complex…
Symbolic Dynamics of Geodesic Flows on Trees
2019
In this chapter, we give a coding of the discrete-time geodesic ow on the nonwandering sets of quotients of locally finite simplicial trees X without terminal vertices by nonelementary discrete subgroups of Aut(X) by a subshift of finite type on a countable alphabet.
On bijections vs. unary functions
1996
A set of finite structures is in Binary NP if it can be characterized by existential second order formulas in which second order quantification is over relations of arity 2. In [DLS95] subclasses of Binary NP were considered, in which the second order quantifiers range only over certain classes of relations. It was shown that many of these subclasses coincide and that all of them can be ordered in a three-level linear hierarchy, the levels of which are represented by bijections, successor relations and unary functions respectively.
Tally languages accepted by alternating multitape finite automata
1997
We consider k-tape 1-way alternating finite automata (k-tape lafa). We say that an alternating automaton accepts a language L\(\subseteq\)(Σ*)k with f(n)-bounded maximal (respectively, minimal) leaf-size if arbitrary (respectively, at least one) accepting tree for any (w1, w2,..., wk) ∈ L has no more than $$f\mathop {(\max }\limits_{1 \leqslant i \leqslant k} \left| {w_i } \right|)$$ leaves. The main results of the paper are the following. If k-tape lafa accepts language L over one-letter alphabet with o(log n)-bounded maximal leaf-size or o(log log n)-bounded minimal leaf-size then the language L is semilinear. Moreover, if a language L is accepted with o(log log(n))-bounded minimal (respe…
A Fast Algorithm Finding the Shortest Reset Words
2013
In this paper we present a new fast algorithm for finding minimal reset words for finite synchronizing automata, which is a problem appearing in many practical applications. The problem is known to be computationally hard, so our algorithm is exponential in the worst case, but it is faster than the algorithms used so far and it performs well on average. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare subsets. Also a number of heuristics are applied. We give both theoretical and practical arguments showing that the effective branching factor is considerably reduced. As a practical test we perform an experimental study of the length of the shortest …
Integer Weighted Regression Tsetlin Machines
2020
The Regression Tsetlin Machine (RTM) addresses the lack of interpretability impeding state-of-the-art nonlinear regression models. It does this by using conjunctive clauses in propositional logic to capture the underlying non-linear frequent patterns in the data. These, in turn, are combined into a continuous output through summation, akin to a linear regression function, however, with non-linear components and binary weights. However, the resolution of the RTM output is proportional to the number of clauses employed. This means that computation cost increases with resolution. To address this problem, we here introduce integer weighted RTM clauses. Our integer weighted clause is a compact r…
FO^2 with one transitive relation is decidable
2013
We show that the satisfiability problem for the two-variable first-order logic, FO^2, over transitive structures when only one relation is required to be transitive, is decidable. The result is optimal, as FO^2 over structures with two transitive relations, or with one transitive and one equivalence relation, are known to be undecidable, so in fact, our result completes the classification of FO^2-logics over transitive structures with respect to decidability. We show that the satisfiability problem is in 2-NExpTime. Decidability of the finite satisfiability problem remains open.