Academic
Publications
Finite Automata and Their Decision Problems

Finite Automata and Their Decision Problems,10.1147/rd.32.0114,Ibm Journal of Research and Development,D. Scott

Finite Automata and Their Decision Problems   (Citations: 504)
BibTex | RIS | RefWorks Download
Journal: Ibm Journal of Research and Development - IBMRD , vol. 3, no. 2, pp. 114-125, 1959
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The research on the state complexity of finite automata had been initiated by Rabin and Scott 23 already in the 1950s, and another early paper is by Lupanov 21...

    Arto Salomaaet al. Undecidability of state complexity

    • ...It is well known that DFAs are equally expressive as NFA and that for any NFA a canonical minimal DFA exists [16]...

    Alessandro Abateet al. Quantitative automata model checking of autonomous stochastic hybrid s...

    • ...Unlike NFAs, which can always be determinized [16], not all WFAs can be determinized...
    • ...Essentially, as in the subset construction for NFA [16], each state in the equivalent DWFA is associated with as et�� of states of the WFA...
    • ...The algorithm MDet is based on the subset construction for determinization of NFAs [16]...

    Benjamin Aminofet al. Rigorous Approximated Determinization of Weighted Automata

    • ...First, we shall trace the origin of this method to its source, which is the celebrated paper of Rabin and Scott [9] that in 1959 introduced the notion of nondeterminism and the power-set construction...
    • ...Frougny’s method and the results of Rabin and Scott [9]...
    • ...comprising all and only the reversals of the strings in L. Frougny’s method is closely connected to the proof by Rabin and Scott [9] that the regular languages are closed under reversal (that is, if L is regular, then L � is also regular)...
    • ...using the notion of nondeterministic finite automata, which was also introduced by Rabin and Scott [9]...
    • ...Clearly, every language recognized by a deterministic finite automaton is also recognized by a nondeterministic finite automaton, since we may take I to be the singleton set fq0g and � ðq;aÞ to be the singleton set f� ðq;aÞg. Theorem 1 (Rabin and Scott [9])...
    • ...language as M. t Corollary 1 (Rabin and Scott [9])...

    Nicholas Pippenger. On-the-Fly Algorithms and Sequential Machines

    • ...Furthermore, two-way two-tape deterministic finite automata (2TFA) and multi-tape finite automata (mTFA) were first introduced by Rabin and Scott in a seminal paper in 1959 [22]...
    • ...In this paper we revisit two-tape two-way deterministic finite automata (2TFA), of which the definition is a little different from the original model introduced by Rabin and Scott in 1959 [22]...
    • ...The definition here is slightly different from the original model introduced by Rabin and Scott [22]...

    Shenggen Zhenget al. Two-Tape Finite Automata with Quantum and Classical States

Sort by: