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.
Displaying 41 –
60 of
186
Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton A is hyper-minimized if no automaton with fewer states is almost equivalent to A. A regular language L is canonical if the minimal automaton accepting L is hyper-minimized. The asymptotic state complexity s∗(L) of a regular language L is the number of states of a hyper-minimized automaton for a language finitely different from L. In this paper we show that: (1) the class...
Two deterministic finite automata are almost equivalent if they disagree in acceptance
only for finitely many inputs. An automaton A is hyper-minimized if no
automaton with fewer states is almost equivalent to A. A regular language
L is canonical if the minimal automaton accepting L is
hyper-minimized. The asymptotic state complexity
s∗(L) of a regular language
L is the number of states of a hyper-minimized automaton for a language
...
We proceed our work on iterated transductions by
studying the closure under
union and composition of some classes of iterated functions. We
analyze this closure for the classes of length-preserving
rational functions, length-preserving subsequential functions and
length-preserving sequential functions with terminal states.
All the classes we
obtain are equal. We also study the connection with deterministic
context-sensitive languages.
Natural algorithms to compute rational expressions for recognizable languages, even those which work well in practice, may produce very long expressions. So, aiming towards the computation of the commutative image of a recognizable language, one should avoid passing through an expression produced this way. We modify here one of those algorithms in order to compute directly a semilinear expression for the commutative image of a recognizable language. We also give a second modification of the algorithm...
Natural algorithms to compute rational expressions for recognizable
languages, even those which work well in practice, may produce very long
expressions. So, aiming towards the computation of the commutative image of a
recognizable language, one should avoid passing through an expression
produced this way.
We modify here one of those algorithms in
order to compute directly a semilinear expression for the commutative image
of a recognizable language. We also give a second
modification of the algorithm...
Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.
Since recognizable tree languages are closed under the rational operations, every regular tree expression denotes a recognizable tree language. We provide an alternative proof to this fact that results in smaller tree automata. To this aim, we transfer Antimirov's partial derivatives from regular word expressions to regular tree expressions. For an analysis of the size of the resulting automaton as well as for algorithmic improvements, we also transfer the methods of Champarnaud and Ziadi from words...
Since recognizable tree languages are closed under the rational
operations, every regular tree expression denotes a recognizable
tree language. We provide an alternative proof to this fact that
results in smaller tree automata. To this aim, we transfer
Antimirov's partial derivatives from regular word expressions to
regular tree expressions. For an analysis of the size of the
resulting automaton as well as for algorithmic improvements, we also
transfer the methods of Champarnaud and Ziadi...
In a previous paper, we have described the construction of an
automaton from a rational expression which has the property that
the automaton built from an expression which is itself computed
from a co-deterministic automaton by the state elimination method
is co-deterministic.
It turned out that the definition on which the construction is
based was inappropriate, and thus the proof of the property was
flawed.
We give here the correct definition of the broken derived terms
of an...
We consider logics on
and which are weaker than
Presburger arithmetic and
we settle the following decision
problem: given a k-ary
relation on and
which are first order definable in
Presburger arithmetic, are they definable in these
weaker logics? These logics, intuitively,
are obtained by considering modulo and threshold counting predicates for differences of two variables.
We consider the defect theorem in the context of labelled
polyominoes, i.e., two-dimensional figures. The classical version of
this property states that if a set of n words is not a code then
the words can be expressed as a product of at most n - 1 words, the
smaller set being a code. We survey several two-dimensional
extensions exhibiting the boundaries where the theorem fails. In
particular, we establish the defect property in the case of three
dominoes (n × 1 or 1 × n rectangles).
We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in space whether the language accepted by an -state non-deterministic automaton is of a star height less than a given integer (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity bound...
We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity...
The notion of pseudovarieties of homomorphisms onto finite monoids was recently introduced by Straubing as an algebraic characterization for certain classes of regular languages. In this paper we provide a mechanism of equational description of these pseudovarieties based on an appropriate generalization of the notion of implicit operations. We show that the resulting metric monoids of implicit operations coincide with the standard ones, the only difference being the actual interpretation of pseudoidentities....
The notion of pseudovarieties of homomorphisms onto finite monoids
was recently introduced by Straubing as an algebraic characterization
for certain classes of regular languages.
In this paper we provide a mechanism of equational description
of these pseudovarieties based on an appropriate
generalization of the notion of implicit operations.
We show that the resulting metric monoids of implicit operations
coincide with the standard ones,
the only difference being the actual interpretation of pseudoidentities.
As...
Currently displaying 41 –
60 of
186