article

Free access

Generalized Pair Algebra With Applications to Automata Theory

Author:

Raymond T. YehAuthors Info & Claims

Journal of the ACM (JACM), Volume 15, Issue 2

Pages 304 - 316

https://doi.org/10.1145/321450.321462

Published: 01 April 1968 Publication History

PDF eReader

Abstract

The concept of a pair algebra is extended so that it can be defined between similar relational systems. It is shown that when the relational systems under consideration are lattices a generalized pair algebra specializes to a pair algebra. Closure properties of generalized pair algebra are investigated and their applications to automata theory are considered.

References

[1]

GINZBURG, A., AND YOELI, M.Products of automata and the problem of covering. Trans. Amer. Math. Soc. 116 (1965), 253-266.

Google Scholar

[2]

HAMMER, P. C. Extended topology: The continuity concepts. Math. Mag. 36, 2 (1963), 101-105.

Google Scholar

[3]

HARTMANIS, J., AND STEARNS, t. E-. Pair algebra and its application to atttomata theory. Inform. Contr. 5 (1962), 252-260.

Google Scholar

[4]

HARTMANIS, J., AND STEARNS, t. E. Algebraic Structure Theory of Sequential Machines. Prentice-HALL, Englewood Cliffs, N. J., 1966.

Crossref

Google Scholar

[5]

LIu, C.L. Pair algebra and its application. IEEE Conference Record of Seventh Annual Symposium on Switching and Automata Theory. IEEE pub. no. 16-C-40, 1966, pp. 103-111.

Google Scholar

[6]

MULLER, D.E. Lecture notes on automata theory. U. of Illinois, Urbana, Ill., 1965.

Google Scholar

[7]

PICKETT, H.E. Direct and subdirect product: Structural theorems for non-deterministic automata. (To appear.)

Google Scholar

[8]

PAULL, M., AND UNGER, S. Minimizing the number of states in incomplete specified sequential functions. IRE Trans. EC-8, (1959), 356-367.

Google Scholar

[9]

YEH, R.T. Weak congruence relations on graphs. Rep. No. 213, Computer Sei. Dept., U. of Illinois, Urbana, Ill., Sept. 1966.

Google Scholar

Cited By

View all

Chang LPoe A(1984)Surjections and coveringsInternational Journal of Computer & Information Sciences10.1007/BF0098582513:6(509-520)Online publication date: Dec-1984
https://doi.org/10.1007/BF00985825
Poe A(1977)Linear N-decompositions and tri-diagonal matricesInformation and Control10.1016/S0019-9958(77)90287-X34:3(210-221)Online publication date: Jul-1977
https://doi.org/10.1016/S0019-9958(77)90287-X
Schwebel JMcCormick B(1970)Consistent properties of composite formation under a binary relationInformation Sciences: an International Journal10.1016/S0020-0255(70)80049-42:2(179-209)Online publication date: 1-Apr-1970
https://dl.acm.org/doi/10.1016/S0020-0255%2870%2980049-4
Show More Cited By

Index Terms

Generalized Pair Algebra With Applications to Automata Theory
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

L-fuzzy automata theory: Some characterizations via general fuzzy operators
Abstract
This paper aims to study the L-fuzzy automata theory based on t-norm, t-conorm and general implicator, alongwith to investigate the algebraic and L-fuzzy topological properties of L-fuzzy automata. Specifically, we introduce L-fuzzy ...
Automata theory based on quantum logic: some characterizations

Automata theory based on quantum logic (abbr. l-valued automata theory) may be viewed as a logical approach of quantum computation. In this paper, we characterize some fundamental properties of l-valued automata theory, and discover that some properties ...
Ideals in constructive Banach algebra theory

We introduce the notion of a 'q-ideal in a commutative Banach algebra, and investigate the relation between q-ideals and maximal ideals constructively.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 15, Issue 2

April 1968

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321450

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1968

Published in JACM Volume 15, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
455
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)2

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chang LPoe A(1984)Surjections and coveringsInternational Journal of Computer & Information Sciences10.1007/BF0098582513:6(509-520)Online publication date: Dec-1984
https://doi.org/10.1007/BF00985825
Poe A(1977)Linear N-decompositions and tri-diagonal matricesInformation and Control10.1016/S0019-9958(77)90287-X34:3(210-221)Online publication date: Jul-1977
https://doi.org/10.1016/S0019-9958(77)90287-X
Schwebel JMcCormick B(1970)Consistent properties of composite formation under a binary relationInformation Sciences: an International Journal10.1016/S0020-0255(70)80049-42:2(179-209)Online publication date: 1-Apr-1970
https://dl.acm.org/doi/10.1016/S0020-0255%2870%2980049-4
Yeh R(1970)Structural equivalence of automataMathematical Systems Theory10.1007/BF016911044:2(198-211)Online publication date: Jun-1970
https://doi.org/10.1007/BF01691104
Liu C(1969)Lattice Functions, Pair Algebras, and Finite-State MachinesJournal of the ACM10.1145/321526.32153316:3(442-454)Online publication date: 1-Jul-1969
https://dl.acm.org/doi/10.1145/321526.321533
Yeh R(1968)Finite Covers with Substitution Property on Infinite AutomataSIAM Journal on Applied Mathematics10.1137/011606416:4(777-782)Online publication date: 1-Jul-1968
https://dl.acm.org/doi/10.1137/0116064
Yeh R(1968)Structural equivalence of automataProceedings of the 9th Annual Symposium on Switching and Automata Theory (swat 1968)10.1109/SWAT.1968.28(405-412)Online publication date: 15-Oct-1968
https://dl.acm.org/doi/10.1109/SWAT.1968.28

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

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

Index Terms

Recommendations

L-fuzzy automata theory: Some characterizations via general fuzzy operators

Automata theory based on quantum logic: some characterizations

Ideals in constructive Banach algebra theory

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations