Based on the characteristics of concrete sulfate attack, a two-dimension cellular automata model is developed based on the fundamental theory of cellular automata to simulate the penetration process of sulfate ion in ...
详细信息
We present a constructive variant of the Hennie machine. It is demonstrated how it can facilitate the design of finite-state machines. We focus on the deterministic version of the model and study its descriptional com...
详细信息
ISBN:
(纸本)9783319049212;9783319049205
We present a constructive variant of the Hennie machine. It is demonstrated how it can facilitate the design of finite-state machines. We focus on the deterministic version of the model and study its descriptional complexity. the model's succinctness is compared with common devices that include the nondeterministic finite automaton, two-way finite automaton and pebble automaton.
We define a complexity measure on non-deterministic Buchi automata, based on the notion of the width of the skeleton tree introduced by Kahler and Wilke. We show that the induced hierarchy tightly correlates to the Wa...
详细信息
ISBN:
(纸本)9783319300009;9783319299990
We define a complexity measure on non-deterministic Buchi automata, based on the notion of the width of the skeleton tree introduced by Kahler and Wilke. We show that the induced hierarchy tightly correlates to the Wagner Hierarchy, a corner stone in the theory of regular omega-languages that is derived from a complexity measure on deterministic Muller automata. the relation between the hierarchies entails, for instance, that a nondeterministic Buchi automaton of width k can be translated to a deterministic parity automaton of degree at most 2k + 1.
We shall consider nondeterministic and deterministic automata equipped with a limited pushdown (constant height NPDAS and DPDAS) as well as their two-way versions (constant height 2NPDAS and 2DPDAS). We show two doubl...
详细信息
ISBN:
(纸本)9783319049212;9783319049205
We shall consider nondeterministic and deterministic automata equipped with a limited pushdown (constant height NPDAS and DPDAS) as well as their two-way versions (constant height 2NPDAS and 2DPDAS). We show two double-exponential gaps for these devices, namely, (i) for complementing constant height one-way NPDAS and (ii) for converting 2NPDAS or 2DPDAS into one-way devices.
One way to generate an accessible deterministic finite automaton is to first generate a spanning tree and then complete it to an automaton. We introduce the ideas of a sequential automaton, that are automata with sequ...
详细信息
In this paper, we consider finite automata withthe restriction that whenever the automaton leaves a state it never returns to it. Equivalently we may assume that the states set is partially ordered and the automaton ...
详细信息
ISBN:
(纸本)3540434534
In this paper, we consider finite automata withthe restriction that whenever the automaton leaves a state it never returns to it. Equivalently we may assume that the states set is partially ordered and the automaton may never move "backwards" to a smaller state. We show that different types of partially-ordered automata characterize different language classes between level 1 and 3/2 of the Straubing-therien-Hierarchy. In particular, we prove that partially-ordered 2-way DFAs recognize exactly the class UL of unambiguous languages introduced by Schutzenberger in 1976. As shown by Schutzenberger, this class coincides withthe class of those languages whose syntactic monoid is in the variety DA, a specific subclass of all "group-free" (or "aperiodic") semigroups. DA has turned out to possess a lot of appealing characterizations. Our result adds one more to these: partially-ordered two-way automata recognize exactly those languages, whose syntactic monoid is in DA.
We consider a problem of labeling a directed multigraph so that it becomes a synchronized finite automaton, as an ultimate goal to solve the famous Road Coloring Conjecture, cf. [1,2]. We introduce a relabeling method...
详细信息
ISBN:
(纸本)3540434534
We consider a problem of labeling a directed multigraph so that it becomes a synchronized finite automaton, as an ultimate goal to solve the famous Road Coloring Conjecture, cf. [1,2]. We introduce a relabeling method which can be used for a large class of automata to improve their "degree of synchronization". this allows, for example, to formulate the conjecture in several equivalent ways.
We show that the image of a regular tree language under a linear bimorphism over binary signatures can be computed in linear time in the size of the input automaton. We do this by transformation into a novel normal fo...
详细信息
ISBN:
(纸本)9783319773131;9783319773124
We show that the image of a regular tree language under a linear bimorphism over binary signatures can be computed in linear time in the size of the input automaton. We do this by transformation into a novel normal form. Our result applies to the translation and parsing complexity of a wide range of grammar formalisms used in computational linguistics, which can now be shown in a uniform way.
Pushdown automata may contain transitions that are never used in any accepting run of the automaton. We present an algorithm for detecting such useless transitions. A finite automaton that captures the possible stack ...
详细信息
ISBN:
(纸本)9783319537320;9783319537337
Pushdown automata may contain transitions that are never used in any accepting run of the automaton. We present an algorithm for detecting such useless transitions. A finite automaton that captures the possible stack content during runs of the pushdown automaton, is first constructed in a forward procedure to determine which transitions are reachable, and then employed in a backward procedure to determine which of these transitions can lead to a final state. An implementation of the algorithm is shown to exhibit a favorable performance.
the automaton theory has been widely applied in many areas of science, such as system simulations, neural networks, etc. It is also a basic theory of compiling routine for discriminating words of a programming languag...
详细信息
ISBN:
(纸本)9781424404759
the automaton theory has been widely applied in many areas of science, such as system simulations, neural networks, etc. It is also a basic theory of compiling routine for discriminating words of a programming language. this paper analyses the equivalence theorem between finite automata and regular expressions, points out the problem existing in the construction rules from finite automata to regular expressions, and proposes further a construction approach from finite automata including multi-node loops to regular expressions. the usage of this theorem and the construction process of regular expressions are expatiated, and the principle of choosing loops and their simplification from finite automata to regular expressions are discussed in detail.
暂无评论