Results 271 to 280 of about 14,469 (313)
Some of the next articles are maybe not open access.
Bell System Technical Journal, 1960
Since it is not clear, in general, how an automaton should best be characterized, one of the purposes of this paper is to find ways to go from one characterization to another. In doing so, we hare not been completely impartial — the programming approach has been emphasized more than the others. There are perhaps two reasons for this emphasis: First and
openaire +1 more source
Since it is not clear, in general, how an automaton should best be characterized, one of the purposes of this paper is to find ways to go from one characterization to another. In doing so, we hare not been completely impartial — the programming approach has been emphasized more than the others. There are perhaps two reasons for this emphasis: First and
openaire +1 more source
DECIDABILITY IN FINITE AUTOMATA
1993In the first part of the paper, applying reduction to the Post Correspondence Problem, it is shown that for deterministic finite two- tape automata --- for which the equivalence problem is decidable --- the inclusion problem is undecidable. Then, the equivalence decision problem for nondeterministic automata with multiplicities is presented and is ...
openaire +2 more sources
1979
Beside the question of nondeterminism the connection between time and space is the most urgent problem in automata theory. In this paper we introduce a new storage medium with properties between space and time: the finite-change tape (FC-tape), a Turing tape, on which every cell can be changed only a bounded number of times.
Burchard von Braunmühl, Rutger Verbeek
openaire +1 more source
Beside the question of nondeterminism the connection between time and space is the most urgent problem in automata theory. In this paper we introduce a new storage medium with properties between space and time: the finite-change tape (FC-tape), a Turing tape, on which every cell can be changed only a bounded number of times.
Burchard von Braunmühl, Rutger Verbeek
openaire +1 more source
Words, Languages & Combinatorics III, 2003
Various quantum versions o f the most basic models o f the classical finite automata have already been introduced and various modes of their computations have already started t o be investigated. In this paper we overview basic models, approaches, techniques and results in this promising area of quantum automata that is expected to play an important ...
Jozef Gruska, Roland Vollmar
openaire +1 more source
Various quantum versions o f the most basic models o f the classical finite automata have already been introduced and various modes of their computations have already started t o be investigated. In this paper we overview basic models, approaches, techniques and results in this promising area of quantum automata that is expected to play an important ...
Jozef Gruska, Roland Vollmar
openaire +1 more source
Canadian Journal of Mathematics, 1965
A finite automaton may be thought of as a possible abstraction of a digital computer. Imagine a tape or sequence of letters from some alphabet being fed into a device with a finite number of internal states. When the device is in a particular state and receives an input letter, the system passes to another internal state and prints a letter on an ...
openaire +2 more sources
A finite automaton may be thought of as a possible abstraction of a digital computer. Imagine a tape or sequence of letters from some alphabet being fed into a device with a finite number of internal states. When the device is in a particular state and receives an input letter, the system passes to another internal state and prints a letter on an ...
openaire +2 more sources
2nd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1961), 1961
This paper concerns switching networks which consist of n identical combinational logic cells interconnected from left to right by alpha communication channels into linear arrays. The synchronous cells in these networks have unit switching delays separating their receipts of external x and left-neighbor alpha inputs from their corresponding productions
Calvin C. Elgot, Joseph D. Rutledge
openaire +1 more source
This paper concerns switching networks which consist of n identical combinational logic cells interconnected from left to right by alpha communication channels into linear arrays. The synchronous cells in these networks have unit switching delays separating their receipts of external x and left-neighbor alpha inputs from their corresponding productions
Calvin C. Elgot, Joseph D. Rutledge
openaire +1 more source
HYBRID EXTENDED FINITE AUTOMATA
International Journal of Foundations of Computer Science, 2006Extended finite automata are finite state automata equipped with the additional ability to apply an operation on the currently remaining input word, depending on the current state. Hybrid extended finite automata can choose from a finite set of such operations.
Henning Bordihn +2 more
openaire +1 more source
On the endomorphisms of finite automata
Mathematical Systems Theory, 1970The properties of endomorphisms and automorphisms of a finite, deterministic automatonA related to the smallest input-independent partition on the set of internal states ofA are investigated. The setH d of all thed-endomorphisms ofA defined here, as well as the setG d of all thed ...
openaire +2 more sources
On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata
2021The paper estimates the number of states in an unambiguous finite automaton (UFA) that is sufficient and in the worst case necessary to simulate an n-state two-way deterministic finite automaton (2DFA). It is proved that a 2DFA with n states can be transformed to a UFA with fewer than \(2^n \cdot n!\) states.
Semyon Petrov, Alexander Okhotin
openaire +1 more source
Applications of Finite Automata
2002We consider three different recent applications of finite automata. They are chosen to emphasize the diversified applicapity of the theory.
openaire +1 more source