The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
We show that the termination of Mohri's algorithm is decidable for polynomially ambiguous weighted finite automata over the tropical
semiring which gives a partial answer to a question by Mohri [29].
The proof relies on an improvement of the notion of the twins property and a Burnside type characterization for the finiteness of the set of states produced by Mohri's algorithm.
In a previous paper, the authors studied the polynomial closure of a variety of languages and gave an algebraic counterpart, in terms of Mal’cev products, of this operation. They also formulated a conjecture about the algebraic counterpart of the boolean closure of the polynomial closure – this operation corresponds to passing to the upper level in any concatenation hierarchy. Although this conjecture is probably true in some particular cases, we give a counterexample in the general case. Another...
In a previous paper, the authors studied the polynomial closure of
a variety of languages and gave an algebraic counterpart, in terms
of Mal'cev products, of this operation. They also formulated a
conjecture about the algebraic counterpart of the boolean closure
of the polynomial closure – this operation corresponds to
passing to the upper level in any concatenation hierarchy.
Although this conjecture is probably true in some particular
cases, we give a counterexample in the general case....
The algebraic counterpart of the Wagner hierarchy consists of a well-founded and decidable classification of finite pointed ω-semigroups of width 2 and height ωω. This paper completes the description of this algebraic hierarchy.
We first give a purely algebraic decidability procedure of this partial ordering by introducing a graph representation of finite pointed ω-semigroups allowing to compute their precise Wagner degrees.
The Wagner degree of any ω-rational language can therefore be computed...
The algebraic study of formal languages shows that ω-rational sets correspond precisely to the ω-languages recognizable by finite ω-semigroups. Within this framework, we provide a construction of the algebraic counterpart of the Wagner hierarchy. We adopt a hierarchical game approach, by translating the Wadge theory from the ω-rational language to the ω-semigroup context. More precisely, we first show that the Wagner degree is indeed a syntactic invariant. We then define a reduction relation on...
It is studied how taking the inverse image
by a sliding block code affects the syntactic semigroup of a sofic
subshift. The main tool are ζ-semigroups, considered as
recognition structures for sofic subshifts.
A new algebraic invariant is obtained for
weak equivalence of sofic subshifts, by
determining which classes of sofic subshifts
naturally defined by pseudovarieties of finite semigroups are closed
under weak equivalence. Among such classes are the classes of almost
finite type subshifts...
Currently displaying 1 –
20 of
225