Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Decision Problem
Finite Automata
Related Publications
(35)
On Relations Defined by Generalized Finite Automata
The Reduction of TwoWay Automata to OneWay Automata
SpaceBounded Reducibility among Combinatorial Problems
The Equivalence Problem for Deterministic TwoTape Automata
Representation of Events in Nerve Nets and Finite Automata
Subscribe
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
Edit
Finite Automata and Their Decision Problems
(
Citations: 504
)
BibTex

RIS

RefWorks
Download
D. Scott
Journal:
Ibm Journal of Research and Development  IBMRD
, vol. 3, no. 2, pp. 114125, 1959
DOI:
10.1147/rd.32.0114
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.
(
ieeexplore.ieee.org
)
Citation Context
(216)
...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 Salomaa
,
et 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 Abate
,
et 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 Aminof
,
et 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 powerset 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
.
OntheFly Algorithms and Sequential Machines
...Furthermore, twoway twotape deterministic finite automata (2TFA) and multitape finite automata (mTFA) were first introduced by Rabin and Scott in a seminal paper in 1959 [
22
]...
...In this paper we revisit twotape twoway 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 Zheng
,
et al.
TwoTape Finite Automata with Quantum and Classical States
Sort by:
Citations
(504)
Undecidability of state complexity
Arto Salomaa
,
Kai Salomaa
,
Sheng Yu
Journal:
International Journal of Computer Mathematics  IJCM
, vol. aheadofp, no. aheadofp, pp. 111, 2012
Quantitative automata model checking of autonomous stochastic hybrid systems
(
Citations: 1
)
Alessandro Abate
,
JoostPieter Katoen
,
Alexandru Mereacre
Published in 2011.
Descriptional and computational complexity of finite automata  A survey
(
Citations: 2
)
Markus Holzer
,
Martin Kutrib
Journal:
Information and Computation/information and Control  IANDC
, vol. 209, no. 3, pp. 456470, 2011
Optimal simulation of selfverifying automata by deterministic automata
(
Citations: 1
)
Galina Jirásková
,
Giovanni Pighizzini
Journal:
Information and Computation/information and Control  IANDC
, vol. 209, no. 3, pp. 528535, 2011
Complexity of multihead finite automata: Origins and directions
(
Citations: 1
)
Markus Holzer
,
Martin Kutrib
,
Andreas Malcher
Journal:
Theoretical Computer Science  TCS
, vol. 412, no. 12, pp. 8396, 2011