article

Finite automata and their decision problems

Authors:

M. O. Rabin,

D. ScottAuthors Info & Claims

IBM Journal of Research and Development, Volume 3, Issue 2

Pages 114 - 125

https://doi.org/10.1147/rd.32.0114

Published: 01 April 1959 Publication History

Abstract

Finite automata are considered in this paper as instruments for classifying finite tapes. Each one-tape automaton defines a set of tapes, a two-tape automaton defines a set of pairs of tapes, et cetera. The structure of the defined sets is studied. Various generalizations of the notion of an automaton are introduced and their relation to the classical automata is determined. Some decision problems concerning automata are shown to be solvable by effective algorithms; others turn out to be unsolvable by algorithms.

References

[1]

A. W. Burks and Hao Wang, "The logic of automata," Journal of the Association for Computing Machinery, 4, 193-218 and 279-297 (1957).

Digital Library

Google Scholar

[2]

S. C. Kleene, "Representation of events in nerve nets and finite automata," Automata Studies, Princeton, pp. 3-41, (1956).

Google Scholar

[3]

W. S. McCulloch and E. Pitts, "A logical calculus of the ideas imminent in nervous activity," Bulletin of Mathematical Biophysics, 5, 115-133 (1943).

Crossref

Google Scholar

[4]

E. F. Moore, "Gedanken-experiments on sequential machines," Automata Studies, Princeton, pp. 129-153 (1956).

Google Scholar

[5]

A. Nerode, "Linear automaton transformations," Proceedings of the American Mathematical Society, 9, 541- 544 (1958).

Crossref

Google Scholar

[6]

E. Post, "A variant of a recursively unsolvable problem," Bulletin of the American Mathematical Society, 52, 264- 268 (1946).

Crossref

Google Scholar

[7]

J. C. Shepherdson, "The reduction of two-way automata to one-way automata," IBM Journal, 3, 198-200 (1959).

Digital Library

Google Scholar

Cited By

View all

Mamouras KChattopadhyay A(2024)Efficient Matching of Regular Expressions with Lookaround AssertionsProceedings of the ACM on Programming Languages10.1145/36329348:POPL(2761-2791)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632934
Zhang YZhang HCao WHe XPark DChoi JPark STsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)LazyBarrier: Reconstructing Android IO Stack for Barrier-Enabled Flash StorageProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640370(601-615)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640370
Mitrana VPăun APăun MCouso J(2024)Jump complexity of finite automata with translucent lettersTheoretical Computer Science10.1016/j.tcs.2024.114450992:COnline publication date: 21-Apr-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114450
Show More Cited By

Finite automata and their decision problems
1. Theory of computation

Recommendations

Alternating finite automata and related problems
The parallel complexity of finite-state automata problems

The goal of this paper is to study the exact complexity of several important problems concerning finite-state automata and to classify the degrees of ambiguity of nondeterministic finite-state automata. Our results are as follows: (1) Minimization of ...
Oblivious two-way finite automata: Decidability and complexity

We investigate the descriptional complexity and decidability of obliviousness for two-way finite automata. In particular, we consider the simulation of two-way deterministic finite automata (2DFAs) by oblivious 2DFAs, the simulation of oblivious 2DFAs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IBM Journal of Research and Development

IBM Journal of Research and Development Volume 3, Issue 2

April 1959

98 pages

ISSN:0018-8646

Issue’s Table of Contents

Publisher

IBM Corp.

United States

Publication History

Published: 01 April 1959

Received: 08 August 1958

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

380
Total Citations
View Citations
8
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mamouras KChattopadhyay A(2024)Efficient Matching of Regular Expressions with Lookaround AssertionsProceedings of the ACM on Programming Languages10.1145/36329348:POPL(2761-2791)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632934
Zhang YZhang HCao WHe XPark DChoi JPark STsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)LazyBarrier: Reconstructing Android IO Stack for Barrier-Enabled Flash StorageProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640370(601-615)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640370
Mitrana VPăun APăun MCouso J(2024)Jump complexity of finite automata with translucent lettersTheoretical Computer Science10.1016/j.tcs.2024.114450992:COnline publication date: 21-Apr-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114450
Zhang K(2024)State-based opacity of labeled real-time automataTheoretical Computer Science10.1016/j.tcs.2023.114373987:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.tcs.2023.114373
Huang WKrafczyk NPeleska J(2024)Exhaustive property oriented model-based testing with symbolic finite state machinesScience of Computer Programming10.1016/j.scico.2023.103005231:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.scico.2023.103005
Zhen LZhang YLi JLi YLi Z(2024)Improved bit-based filtering algorithm for regular constraintExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.121259235:COnline publication date: 10-Jan-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121259
Susik RNowotniak R(2024)Pattern matching algorithms in blockchain for network fees reductionThe Journal of Supercomputing10.1007/s11227-024-06115-880:12(17741-17759)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s11227-024-06115-8
Pighizzini GPrigioniero LSádovský Š(2024)Performing Regular Operations with 1-Limited AutomataTheory of Computing Systems10.1007/s00224-024-10163-168:3(465-486)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00224-024-10163-1
Paul E(2024)Finite Sequentiality of Finitely Ambiguous Max-Plus Tree AutomataTheory of Computing Systems10.1007/s00224-021-10049-668:4(615-661)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00224-021-10049-6
Lambert D(2024)System Description: A Theorem-Prover for Subregular Systems: The Language Toolkit and Its Interpreter, PlebbyFunctional and Logic Programming10.1007/978-981-97-2300-3_16(311-328)Online publication date: 15-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2300-3_16
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

Alternating finite automata and related problems

The parallel complexity of finite-state automata problems

Oblivious two-way finite automata: Decidability and complexity

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations