Search results for "push"
showing 10 items of 121 documents
Simulation is decidable for one-counter nets
1998
We prove that the simulation preorder is decidable for the class of one-counter nets. A one-counter net consists of a finite-state machine operating on a variable (counter) which ranges over the natural numbers. Each transition can increase or decrease the value of the counter. A transition may not be performed if this implies that the value of the counter becomes negative. The class of one-counter nets is computationally equivalent to the class of Petri nets with one unbounded place, and to the class of pushdown automata where the stack alphabet is restricted to one symbol. To our knowledge, this is the first result in the literature which gives a positive answer to the decidability of sim…
Superiority Of One-Way And Realtime Quantum Machines
2012
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 architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime push…
Automata and differentiable words
2011
We exhibit the construction of a deterministic automaton that, given k > 0, recognizes the (regular) language of k-differentiable words. Our approach follows a scheme of Crochemore et al. based on minimal forbidden words. We extend this construction to the case of C\infinity-words, i.e., words differentiable arbitrary many times. We thus obtain an infinite automaton for representing the set of C\infinity-words. We derive a classification of C\infinity-words induced by the structure of the automaton. Then, we introduce a new framework for dealing with \infinity-words, based on a three letter alphabet. This allows us to define a compacted version of the automaton, that we use to prove that ev…
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata
2007
It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.
Quantum Pushdown Automata
2000
Quantum finite automata, as well as quantum pushdown automata were first introduced by C. Moore, J. P. Crutchfield [13]. In this paper we introduce the notion of quantum pushdown automata (QPA) in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [11]. It is established that the unitarity criteria of QPA are not equivalent to the corresponding unitarity criteria of quantum Turing machines [4]. We show that QPA can recognize every regular language. Finally we present some simple languages recognized by QPA, two of them are not recognizable by deterministic pushdown automata and one seems to be not recognizable by probabilistic pushdown …
TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
2013
We examine the minimum amount of memory for real-time, as opposed to one-way, computation accepting nonregular languages. We consider deterministic, nondeterministic and alternating machines working within strong, middle and weak space, and processing general or unary inputs. In most cases, we are able to show that the lower bounds for one-way machines remain tight in the real-time case. Memory lower bounds for nonregular acceptance on other devices are also addressed. It is shown that increasing the number of stacks of real-time pushdown automata can result in exponential improvement in the total amount of space usage for nonregular language recognition.
A graph theoretic approach to automata minimality
2012
AbstractThe paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F. We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.
Uncertainty and cross-border banking flows
2019
Abstract While global uncertainty—measured by the VIX—has proven to be a robust global “push” factor of international capital flows, there has been no systematic study assessing the role of uncertainty in driving bilateral capital flows. This paper examines the effects of higher country-specific uncertainty on cross-border banking flows using data from the Bank for International Settlements Locational Banking Statistics. The bilateral structure of this data allows disentangling supply factors from demand factors, thereby helping identify the effect of higher uncertainty on cross-border banking flows from other confounding factors. The results of this analysis suggest that: (i) uncertainty i…
Definition of Seismic Vulnerability Maps for Civil Protection Systems: The Case of Lampedusa Island
2016
The opportunity to locate and quantify the major criticalities associated to natural catastrophic events on a territory allows to plan adequate strategies and interventions by civil protection bodies involved in local and international emergencies. Seismic risk depends, most of all, on the vulnerability of buildings belonging to the urban areas. For this reason, the definition, by a deep analysis of the territory, of instruments identifying and locating vulnerability, largely favours the activities of institutions appointed to safeguard the safety of citizens. This paper proposes a procedure for the definition of vulnerability maps in terms of vulnerability indexes and critical peak ground …
Review of push-out and shear response of hybrid steel-trussed concrete beams
2018
The hybrid steel trussed concrete beams examined in the present study are comprised of two principal components, i.e., a steel joist with inclined rebars, realized in industry, which is welded to a smooth steel plate and then embedded within the concrete cast in situ. The paper presents first the state of the art on laboratory tests and analytical modeling of the steel-to-concrete stress transfer mechanism investigated by push-out tests. Next, the most relevant scientific contributions currently available in the technical literature regarding experimental investigation on actual shear behavior are summarized and discussed. Lastly codes and analytical models are reviewed.