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.
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.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Bertoni et al. introduced in Lect. Notes Comput. Sci.2710 (2003) 1–20 a new model of 1-way quantum finite
automaton (1qfa) called 1qfa with control language (1qfc). This model,
whose recognizing power is exactly the class of regular languages, generalizes
main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide
algorithms for constructing 1qfc's accepting the inverse homomorphic images
and quotients of languages accepted...
Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first exponential...
Branching programs are a well established computation model for
Boolean functions, especially read-once branching programs have
been studied intensively.
In this paper the expressive power of nondeterministic read-once branching
programs, more precisely the class of functions
representable in polynomial size, is investigated.
For that reason two restricted models of nondeterministic read-once
branching programs are defined and a lower bound method is presented.
Furthermore, the first exponential...
We present a categorical formulation
of the rewriting of possibly cyclic term graphs, based on a
variation of algebraic 2-theories. We show that
this presentation is equivalent to the well-accepted
operational definition proposed by Barendregt et al. – but
for the
case of circular redexes , for which we propose (and
justify formally) a different treatment.
The categorical framework allows us to model in a concise way
also automatic garbage collection
and rules
for sharing/unsharing and...
Wang automata are devices for picture language recognition recently introduced by us, which characterize the class REC of recognizable picture languages. Thus, Wang automata are equivalent to tiling systems or online tessellation acceptors, and are based like Wang systems on labeled Wang tiles. The present work focus on scanning strategies, to prove that the ones Wang automata are based on are those following four kinds of movements: boustrophedonic, “L-like”, “U-like”, and spirals.
Wang automata are devices for picture language
recognition recently introduced by us, which characterize the class
REC of recognizable picture languages. Thus, Wang automata are
equivalent to tiling systems or online tessellation acceptors, and
are based like Wang systems on labeled Wang tiles. The present work
focus on scanning strategies, to prove that the ones Wang automata
are based on are those following four kinds of movements:
boustrophedonic, “L-like”, “U-like”, and spirals.
In automata theory, quantum computation has been widely examined for finite state
machines, known as quantum finite automata (QFAs), and less attention has been given to
QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of
QFAs where the input head operates in one-way or realtime mode, and present some new
results regarding their superiority over their classical counterparts. Our first result is
about the nondeterministic...
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model...
In automata theory, quantum computation has been widely examined for finite state
machines, known as quantum finite automata (QFAs), and less attention has been given to
QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of
QFAs where the input head operates in one-way or realtime mode, and present some new
results regarding their superiority over their classical counterparts. Our first result is
about the nondeterministic...
We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.
We describe the communicating alternating machines and their
simulation. We show that, in the case of communicating alternating
machines which are bounded, simultaneously, by polynomial time and
logarithmic space, the use of three communication levels instead
of two does not increase computational power of communicating
alternating machines. This resolves an open problem [2]
concerning the exact position of machines with three communication
levels in the hierarchy.
We add sequential operations to the categorical algebra of weighted and Markov automata introduced in [L. de Francesco Albasini, N. Sabadini and R.F.C. Walters,
arXiv:0909.4136]. The extra expressiveness of the algebra permits the description of hierarchical systems, and ones with evolving geometry. We make a comparison with the probabilistic automata of Lynch et al. [SIAM J. Comput. 37 (2007) 977–1013].
We add sequential operations to the categorical algebra of weighted and
Markov automata introduced in [L. de Francesco Albasini, N. Sabadini and R.F.C. Walters,
arXiv:0909.4136]. The extra
expressiveness of
the algebra permits the description of hierarchical systems, and ones with
evolving geometry. We make a comparison with the probabilistic automata of
Lynch et al. [SIAM J. Comput.37 (2007) 977–1013].
Currently displaying 61 –
80 of
88