article

Principal AFL

Authors:

Seymour Ginsburg,

Sheila GreibachAuthors Info & Claims

Journal of Computer and System Sciences, Volume 4, Issue 4

Pages 308 - 338

https://doi.org/10.1016/S0022-0000(70)80016-2

Published: 01 August 1970 Publication History

Abstract

A (full) principal AFL is a (full) AFL generated by a single language, i.e., it is thesmallest (full) AFL containing the given language. In the present paper, a study is made of such AFL. First, an AFA (abstract family of acceptors) characterization of (full) principal AFL is given. From this result, many well-known families of AFL can be shown to be (full) principal AFL. Next, two representation theorems for each language in a (full) principal AFL are given. The first involves the generator and one application each of concatenation, star, intersection with a regular set, inverse homomorphism, and a special type of homomorphism. The second involves an a-transducer, the generator, and one application of concatenation and star. Finally, it is shown that if @?"1 and @?"2 are (full) principal AFL, then so are (a) the smallest (full) AFL containing {L"1@?L"2/L"1 in @?"1, L"2 in @?"2 and (b) the family obtained by substituting @e-free languages of @?"2 into languages of @?"1.

References

[1]

Nested Stack Automata. J. Assoc. Comput. Mach. v19. 383-406.

Google Scholar

[2]

On Certain Formal Properties of Grammars. Information and Control. v2. 137-167.

Google Scholar

[3]

Context-Free Grammars and Pushdown Storage. MIT Research Laboratory of Electronics, Quarterly Progress Report. v65. 187-194.

Google Scholar

[4]

***Abstract Families of Languages,*** Studies in Abstract Families of Languages. Mem. Amer. Math. Soc., Memoir. v87. 41-51.

Google Scholar

[5]

Finite-Turn Pushdown Automata. SIAM J. of Control. v4. 429-453.

Google Scholar

[6]

Substitution in Families of Languages. Information Sciences. v2. 83-110.

Crossref

Google Scholar

[7]

A New Normal-Form Theorem for Context-Free Phrase Structure Grammars. Journal of the Association for Computing Machinery. v12. 42-52.

Crossref

Google Scholar

[8]

An Infinite Hierarchy of Context-Free Grammars. J. Assoc. Comput. Mach. v16. 91-106.

Crossref

Google Scholar

[9]

Checking Automata and One-Way Stack Languages. J. Comput. System Sci. v3. 196-217.

Crossref

Google Scholar

[10]

Multitape AFA, SDC document TM-738/051/00.

Google Scholar

[11]

***Independence of AFL Operations,*** Studies in Abstract Families of Languages. Mem. Amer. Math. Soc. Memoir. v87. 33-40.

Google Scholar

[12]

Hierarchies of Memory Limited Computations. In: Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pp. 179-190.

Crossref

Google Scholar

Cited By

View all

Okubo FFujioka KYokomori T(2022)Chemical Reaction Regular GrammarsNew Generation Computing10.1007/s00354-022-00160-840:2(659-680)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/s00354-022-00160-8
Fang ZDeogun JJehn LCrum L(1986)Closure properties of certain classes of languages under bi-language formProceedings of the 1986 ACM fourteenth annual conference on Computer science10.1145/324634.325252Online publication date: 1-Feb-1986
https://dl.acm.org/doi/10.1145/324634.325252
Rodriguez F(1981)Indépendance forte de certaines opérationsActa Informatica10.1007/BF0028896315:2(153-166)Online publication date: 1-Jun-1981
https://dl.acm.org/doi/10.1007/BF00288963
Show More Cited By

Principal AFL
1. Theory of computation
  1. Formal languages and automata theory

Recommendations

Two-way a-transducers and AFL

For each (abstract family of languages) AFL @__ __, two families of languages, the family @__ __(@__ __) of nondeterministic and the family of deterministic two-way a-transducer mappings of languages in @__ __ are defined. For each (abstract family of ...
Uniformly erasable AFL

A full AFL is uniformly -erasable if in every AFA defining (where each automaton signals acceptance by simultaneously entering an accepting state and emptying its storage), the quasi-realtime acceptors also define . This is equivalent to the property ...
AFL with the semilinear property

A slip language is a language whose Parikh mapping is a semilinear set. A slip family is a family containing only slip languages. The purpose of this paper is to study slip AFL. A sufficiency condition is given on a slip family which ensures that the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 4, Issue 4

August, 1970

85 pages

ISSN:0022-0000

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 August 1970

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Okubo FFujioka KYokomori T(2022)Chemical Reaction Regular GrammarsNew Generation Computing10.1007/s00354-022-00160-840:2(659-680)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/s00354-022-00160-8
Fang ZDeogun JJehn LCrum L(1986)Closure properties of certain classes of languages under bi-language formProceedings of the 1986 ACM fourteenth annual conference on Computer science10.1145/324634.325252Online publication date: 1-Feb-1986
https://dl.acm.org/doi/10.1145/324634.325252
Rodriguez F(1981)Indépendance forte de certaines opérationsActa Informatica10.1007/BF0028896315:2(153-166)Online publication date: 1-Jun-1981
https://dl.acm.org/doi/10.1007/BF00288963
Autebert J(1979)Opérations de cylindre et applications séquentielles gauches inversesActa Informatica10.1007/BF0028907011:3(241-258)Online publication date: 1-Sep-1979
https://dl.acm.org/doi/10.1007/BF00289070
Book RNivat M(1978)Linear Languages and the Intersection Closures of Classes of LanguagesSIAM Journal on Computing10.1137/02070167:2(167-177)Online publication date: 1-May-1978
https://dl.acm.org/doi/10.1137/0207016
Greibach S(1978)Hierarchy theorems for two-way finite state transducersActa Informatica10.1007/BF0026460311:1(89-101)Online publication date: 1-Mar-1978
https://dl.acm.org/doi/10.1007/BF00264603
Ginsburg SGoldstine JGreibach S(1975)Uniformly erasable AFLJournal of Computer and System Sciences10.1016/S0022-0000(75)80038-910:2(165-182)Online publication date: 1-Apr-1975
https://dl.acm.org/doi/10.1016/S0022-0000%2875%2980038-9
Greibach S(1974)Jump PDA’s and Hierarchies of Deterministic Context-Free LanguagesSIAM Journal on Computing10.1137/02030093:2(111-127)Online publication date: 1-Jun-1974
https://dl.acm.org/doi/10.1137/0203009
Greibach SAho ABorodin AConstable RFloyd RHarrison MKarp RStrong H(1973)Jump PDA's, deterministic context-free languages principal AFDLs and polynomial time recognition—(Extended Abstract)Proceedings of the fifth annual ACM symposium on Theory of computing10.1145/800125.804031(20-28)Online publication date: 30-Apr-1973
https://dl.acm.org/doi/10.1145/800125.804031
Boasson LCrestin JNivat M(1973)Familles de langages translatables et fermées par crochetActa Informatica10.1007/BF002895062:4(383-393)Online publication date: 1-Dec-1973
https://dl.acm.org/doi/10.1007/BF00289506
Show More Cited By

Abstract

References

Cited By

Recommendations

Two-way a-transducers and AFL

Uniformly erasable AFL

AFL with the semilinear property

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations