×

Greibach, Sheila A.

Author ID: greibach.sheila-a Recent zbMATH articles by "Greibach, Sheila A."
Published as: Greibach, S. A.; Greibach, Sheila A.; Greibach, S.; Greibach, Sheila; Greibach, Sh. A.
Documents Indexed: 75 Publications since 1963, including 3 Books
Co-Authors: 16 Co-Authors with 37 Joint Publications
413 Co-Co-Authors

Publications by Year

Citations contained in zbMATH Open

65 Publications have been cited 1,456 times in 840 Documents Cited by Year
Remarks on blind and partially blind one-way multicounter machines. Zbl 0389.68030
Greibach, S. A.
102
1978
Deterministic context free languages. Zbl 0145.00802
Ginsburg, S.; Greibach, S.
85
1966
One-way stack automata. Zbl 0171.14803
Ginsburg, Seymour; Greibach, Sheila A.; Harrison, Michael A.
85
1967
Studies in abstract families of languages. Zbl 0194.31402
Ginsburg, Seymour; Greibach, Sheila; Hopcroft, John
69
1969
The hardest context-free language. Zbl 0278.68073
Greibach, Sheila A.
61
1973
A new normal-form theorem for context-free phrase structure grammars. Zbl 0135.18404
Greibach, S. A.
61
1965
Checking automata and one-way stack languages. Zbl 0174.02702
Greibach, S.
58
1969
Principal AFL. Zbl 0198.03102
Ginsburg, S.; Greibach, S.
54
1970
Scattered context grammars. Zbl 0174.02801
Greibach, S.; Hopcroft, J.
54
1969
An infinite hierarchy of context-free languages. Zbl 0182.02002
Greibach, S. A.
53
1969
Quasi-real-time languages. Zbl 0188.33102
Book, R. V.; Greibach, S. A.
51
1970
Theory of program structures: Schemes, semantics, verification. Zbl 0345.68002
Greibach, Sheila A.
45
1975
Full AFLs and nested iterated substitution. Zbl 0188.03102
Greibach, S. A.
44
1970
Chains of full AFL’s. Zbl 0203.30102
Greibach, S. A.
41
1970
Stack automata and compiling. Zbl 0153.01101
Ginsburg, Seymour; Greibach, Sheila A.; Harrison, Michael A.
39
1967
Abstract families of languages. Zbl 0308.68058
Ginsburg, S.; Greibach, S.
37
1975
One way finite visit automata. Zbl 0368.68059
Greibach, S. A.
33
1978
Remarks on the complexity of nondeterministic counter languages. Zbl 0332.68039
Greibach, S. A.
29
1976
The unsolvability of the recognition of linear context-free languages. Zbl 0148.00901
Greibach, Sheila A.
29
1966
Ambiguity in graphs and expressions. Zbl 0222.94067
Book, Ronald; Even, Shimon; Greibach, Sheila; Ott, Gene
27
1971
A note on undecidable properties of formal languages. Zbl 0157.01902
Greibach, S.
27
1968
Syntactic operators on full semiAFLs. Zbl 0269.68046
Greibach, Sheila A.
26
1972
Time- and tape-bounded Turing acceptors and AFLs. Zbl 0206.28702
Book, R. V.; Greibach, S. A.; Wegbreit, B.
23
1970
Control sets on context-free grammar forms. Zbl 0359.68093
Greibach, S. A.
20
1977
Reset machines. Zbl 0427.03029
Book, Ronald V.; Greibach, Sheila A.; Wrathall, Celia
19
1979
Jump PDA’s and hierarchies of deterministic context-free languages. Zbl 0288.68031
Greibach, S. A.
19
1974
Mappings which preserve context sensitive languages. Zbl 0145.00803
Ginsburg, S.; Greibach, S. A.
19
1966
Superdeterministic PDAs: A subcase with a decidable inclusion problem. Zbl 0462.68030
Greibach, S. A.; Friedman, E. P.
18
1980
A note on pushdown store automata and regular systems. Zbl 0183.01703
Greibach, S. A.
18
1967
One counter languages and the IRS condition. Zbl 0307.68062
Greibach, S. A.
17
1975
Erasable context-free languages. Zbl 0317.68059
Greibach, S. A.
16
1975
Multitape AFA. Zbl 0241.68031
Greibach, Sheila; Ginsburg, Seymour
14
1972
The undecidability of the ambiguity problem for minimal linear grammars. Zbl 0115.37007
Greibach, Sh. A.
14
1963
Superdeterministic DPDAs: The method of accepting does affect decision problems. Zbl 0419.68100
Friedman, E. P.; Greibach, S. A.
12
1979
Some uniformly erasable families of languages. Zbl 0343.68033
Ginsburg, Seymour; Goldstine, Jonathan; Greibach, Sheila
11
1976
Erasing in context-free AFLs. Zbl 0248.68036
Greibach, S. A.
10
1972
Uniformly erasable AFL. Zbl 0325.68042
Ginsburg, Seymour; Goldstine, Jonathan; Greibach, Sheila
10
1975
Visits, crosses, and reversals for nondeterministic off-line machines. Zbl 0375.02027
Greibach, S. A.
9
1978
A polynomial time algorithm for deciding the equivalence problem for 2- tape deterministic finite state acceptors. Zbl 0497.68050
Friedman, E. P.; Greibach, S. A.
9
1982
Hierarchy theorems for two-way finite state transducers. Zbl 0398.68038
Greibach, S. A.
8
1978
Tape-bounded Turing acceptors and principal AFLs. Zbl 0206.28703
Book, R. V.; Greibach, S. A.; Ibarra, O. H.; Wegbreit, B.
8
1970
Linearity is polynomially decidable for realtime pushdown store automata. Zbl 0413.68086
Greibach, S. A.
7
1979
On AFL generators for finitely encoded AFA. Zbl 0249.68025
Ginsburg, Seymour; Greibach, Sheila
7
1973
Characteristic and ultrarealtime languages. Zbl 0216.23803
Greibach, S. A.
6
1971
A generalization of Parikh’s semilinear theorem. Zbl 0251.68043
Greibach, S. A.
6
1972
Comparisons and reset machines. Zbl 0388.03017
Book, Ronald V.; Greibach, Sheila A.; Wrathall, Celia
4
1978
The independence of certain operations on semi-AFLs. Zbl 0388.68068
Book, Ronald V.; Greibach, Sheila A.
4
1978
One counter languages and the Chevron operation. Zbl 0441.68081
Greibach, S. A.
4
1979
Some restrictions on W-grammars. Zbl 0288.68035
Greibach, Sheila A.
4
1974
Single tree grammars. Zbl 0765.68071
Greibach, Sheila; Shi, Weiping; Simonson, Shai
3
1992
The strong independence of substitution and homomorphic replication. Zbl 0387.68048
Greibach, S. A.
3
1978
Comments on universal and left universal grammars, context-sensitive languages, and context-free grammar forms. Zbl 0387.68059
Greibach, S. A.
3
1978
On equivalence and subclass containment problems for deterministic context-free languages. Zbl 0392.68069
Friedman, E. P.; Greibach, S. A.
3
1978
A remark on code sets and context-free languages. Zbl 0307.68058
Greibach, S. A.
3
1975
A note on the best-case complexity. Zbl 0672.68019
Rolim, José D. P.; Greibach, Sheila A.
2
1989
Monadic recursion schemes: The effect of constants. Zbl 0411.03010
Friedman, Emily P.; Greibach, Sheila A.
2
1979
Ambiguity in graphs and expressions. Zbl 0294.94028
Book, R.; Even, S.; Greibach, S.; Ott, G.
2
1969
Principal AFL. Zbl 0308.68059
Ginsburg, S.; Greibach, S.
2
1975
Single-tape reset machines. Zbl 0585.68073
Greibach, S. A.; Wrathall, C.
1
1986
On the IO-complexity and approximation languages. Zbl 0659.03023
Rolim, José D. P.; Greibach, Sheila A.
1
1988
Formal languages: origins and directions. Zbl 0998.01515
Greibach, S. A.
1
1981
A note on undecidable properties of formal languages. Zbl 0307.68055
Greibach, S.
1
1975
Quasi-realtime languages (extended abstract). Zbl 1282.68152
Book, Ronald V.; Greibach, Sheila A.
1
1969
Formal parsing systems. Zbl 0123.12602
Greibach, Sheila A.
1
1964
Matching and spanning in certain planar graphs. Zbl 0527.05053
Carlyle, J. W.; Greibach, S. A.; Paz, A.
1
1983
Single tree grammars. Zbl 0765.68071
Greibach, Sheila; Shi, Weiping; Simonson, Shai
3
1992
A note on the best-case complexity. Zbl 0672.68019
Rolim, José D. P.; Greibach, Sheila A.
2
1989
On the IO-complexity and approximation languages. Zbl 0659.03023
Rolim, José D. P.; Greibach, Sheila A.
1
1988
Single-tape reset machines. Zbl 0585.68073
Greibach, S. A.; Wrathall, C.
1
1986
Matching and spanning in certain planar graphs. Zbl 0527.05053
Carlyle, J. W.; Greibach, S. A.; Paz, A.
1
1983
A polynomial time algorithm for deciding the equivalence problem for 2- tape deterministic finite state acceptors. Zbl 0497.68050
Friedman, E. P.; Greibach, S. A.
9
1982
Formal languages: origins and directions. Zbl 0998.01515
Greibach, S. A.
1
1981
Superdeterministic PDAs: A subcase with a decidable inclusion problem. Zbl 0462.68030
Greibach, S. A.; Friedman, E. P.
18
1980
Reset machines. Zbl 0427.03029
Book, Ronald V.; Greibach, Sheila A.; Wrathall, Celia
19
1979
Superdeterministic DPDAs: The method of accepting does affect decision problems. Zbl 0419.68100
Friedman, E. P.; Greibach, S. A.
12
1979
Linearity is polynomially decidable for realtime pushdown store automata. Zbl 0413.68086
Greibach, S. A.
7
1979
One counter languages and the Chevron operation. Zbl 0441.68081
Greibach, S. A.
4
1979
Monadic recursion schemes: The effect of constants. Zbl 0411.03010
Friedman, Emily P.; Greibach, Sheila A.
2
1979
Remarks on blind and partially blind one-way multicounter machines. Zbl 0389.68030
Greibach, S. A.
102
1978
One way finite visit automata. Zbl 0368.68059
Greibach, S. A.
33
1978
Visits, crosses, and reversals for nondeterministic off-line machines. Zbl 0375.02027
Greibach, S. A.
9
1978
Hierarchy theorems for two-way finite state transducers. Zbl 0398.68038
Greibach, S. A.
8
1978
Comparisons and reset machines. Zbl 0388.03017
Book, Ronald V.; Greibach, Sheila A.; Wrathall, Celia
4
1978
The independence of certain operations on semi-AFLs. Zbl 0388.68068
Book, Ronald V.; Greibach, Sheila A.
4
1978
The strong independence of substitution and homomorphic replication. Zbl 0387.68048
Greibach, S. A.
3
1978
Comments on universal and left universal grammars, context-sensitive languages, and context-free grammar forms. Zbl 0387.68059
Greibach, S. A.
3
1978
On equivalence and subclass containment problems for deterministic context-free languages. Zbl 0392.68069
Friedman, E. P.; Greibach, S. A.
3
1978
Control sets on context-free grammar forms. Zbl 0359.68093
Greibach, S. A.
20
1977
Remarks on the complexity of nondeterministic counter languages. Zbl 0332.68039
Greibach, S. A.
29
1976
Some uniformly erasable families of languages. Zbl 0343.68033
Ginsburg, Seymour; Goldstine, Jonathan; Greibach, Sheila
11
1976
Theory of program structures: Schemes, semantics, verification. Zbl 0345.68002
Greibach, Sheila A.
45
1975
Abstract families of languages. Zbl 0308.68058
Ginsburg, S.; Greibach, S.
37
1975
One counter languages and the IRS condition. Zbl 0307.68062
Greibach, S. A.
17
1975
Erasable context-free languages. Zbl 0317.68059
Greibach, S. A.
16
1975
Uniformly erasable AFL. Zbl 0325.68042
Ginsburg, Seymour; Goldstine, Jonathan; Greibach, Sheila
10
1975
A remark on code sets and context-free languages. Zbl 0307.68058
Greibach, S. A.
3
1975
Principal AFL. Zbl 0308.68059
Ginsburg, S.; Greibach, S.
2
1975
A note on undecidable properties of formal languages. Zbl 0307.68055
Greibach, S.
1
1975
Jump PDA’s and hierarchies of deterministic context-free languages. Zbl 0288.68031
Greibach, S. A.
19
1974
Some restrictions on W-grammars. Zbl 0288.68035
Greibach, Sheila A.
4
1974
The hardest context-free language. Zbl 0278.68073
Greibach, Sheila A.
61
1973
On AFL generators for finitely encoded AFA. Zbl 0249.68025
Ginsburg, Seymour; Greibach, Sheila
7
1973
Syntactic operators on full semiAFLs. Zbl 0269.68046
Greibach, Sheila A.
26
1972
Multitape AFA. Zbl 0241.68031
Greibach, Sheila; Ginsburg, Seymour
14
1972
Erasing in context-free AFLs. Zbl 0248.68036
Greibach, S. A.
10
1972
A generalization of Parikh’s semilinear theorem. Zbl 0251.68043
Greibach, S. A.
6
1972
Ambiguity in graphs and expressions. Zbl 0222.94067
Book, Ronald; Even, Shimon; Greibach, Sheila; Ott, Gene
27
1971
Characteristic and ultrarealtime languages. Zbl 0216.23803
Greibach, S. A.
6
1971
Principal AFL. Zbl 0198.03102
Ginsburg, S.; Greibach, S.
54
1970
Quasi-real-time languages. Zbl 0188.33102
Book, R. V.; Greibach, S. A.
51
1970
Full AFLs and nested iterated substitution. Zbl 0188.03102
Greibach, S. A.
44
1970
Chains of full AFL’s. Zbl 0203.30102
Greibach, S. A.
41
1970
Time- and tape-bounded Turing acceptors and AFLs. Zbl 0206.28702
Book, R. V.; Greibach, S. A.; Wegbreit, B.
23
1970
Tape-bounded Turing acceptors and principal AFLs. Zbl 0206.28703
Book, R. V.; Greibach, S. A.; Ibarra, O. H.; Wegbreit, B.
8
1970
Studies in abstract families of languages. Zbl 0194.31402
Ginsburg, Seymour; Greibach, Sheila; Hopcroft, John
69
1969
Checking automata and one-way stack languages. Zbl 0174.02702
Greibach, S.
58
1969
Scattered context grammars. Zbl 0174.02801
Greibach, S.; Hopcroft, J.
54
1969
An infinite hierarchy of context-free languages. Zbl 0182.02002
Greibach, S. A.
53
1969
Ambiguity in graphs and expressions. Zbl 0294.94028
Book, R.; Even, S.; Greibach, S.; Ott, G.
2
1969
Quasi-realtime languages (extended abstract). Zbl 1282.68152
Book, Ronald V.; Greibach, Sheila A.
1
1969
A note on undecidable properties of formal languages. Zbl 0157.01902
Greibach, S.
27
1968
One-way stack automata. Zbl 0171.14803
Ginsburg, Seymour; Greibach, Sheila A.; Harrison, Michael A.
85
1967
Stack automata and compiling. Zbl 0153.01101
Ginsburg, Seymour; Greibach, Sheila A.; Harrison, Michael A.
39
1967
A note on pushdown store automata and regular systems. Zbl 0183.01703
Greibach, S. A.
18
1967
Deterministic context free languages. Zbl 0145.00802
Ginsburg, S.; Greibach, S.
85
1966
The unsolvability of the recognition of linear context-free languages. Zbl 0148.00901
Greibach, Sheila A.
29
1966
Mappings which preserve context sensitive languages. Zbl 0145.00803
Ginsburg, S.; Greibach, S. A.
19
1966
A new normal-form theorem for context-free phrase structure grammars. Zbl 0135.18404
Greibach, S. A.
61
1965
Formal parsing systems. Zbl 0123.12602
Greibach, Sheila A.
1
1964
The undecidability of the ambiguity problem for minimal linear grammars. Zbl 0115.37007
Greibach, Sh. A.
14
1963
all top 5

Cited by 662 Authors

51 Ibarra, Oscar H.
30 Greibach, Sheila A.
28 Kutrib, Martin
22 Engelfriet, Joost
22 McQuillan, Ian
19 Book, Ronald Vernon
16 Ginsburg, Seymour
16 Meduna, Alexander
16 Okhotin, Alexander
16 Rozenberg, Grzegorz
13 Boasson, Luc
13 Latteux, Michel
12 Beauquier, Joffroy
11 Sénizergues, Géraud
10 Autebert, Jean-Michel
10 Goldstine, Jonathan
10 Inoue, Katsushi
10 Malcher, Andreas
10 Zetzsche, Georg
9 Fernau, Henning
9 Holzer, Markus
9 Hromkovič, Juraj
9 Otto, Friedrich
9 Vogler, Heiko
8 Jantzen, Matthias
8 Păun, Gheorghe
8 Ravikumar, Bala
8 Salomaa, Kai T.
8 Wood, Derick
7 Brandenburg, Franz-Josef
7 Hunt, Harry Bowen III
7 Takanami, Itsuo
7 Wotschke, Detlef
7 Wrathall, Celia
6 Crespi Reghizzi, Stefano
6 D’Alessandro, Flavio
6 Ehrenfeucht, Andrzej
6 Friedman, Emily P.
6 Hopcroft, John Edward H.
6 Karhumaki, Juhani
6 Slutzki, Giora
6 Spanier, Edwin Henry
6 Ullman, Jeffrey David
6 Wendlandt, Matthias
5 Bergstra, Jan A.
5 Bordihn, Henning
5 Culik, Karel II
5 Gallier, Jean H.
5 Kambites, Mark
5 McKenzie, Pierre
5 Mitrana, Victor
5 Nivat, Maurice
5 Scarcello, Francesco
5 Turakainen, Paavo
5 Yakaryılmaz, Abuzer
4 Aho, Alfred Vaino
4 Asveld, Peter R. J.
4 Bensch, Suna
4 Bhaskar, Siddharth
4 Blattner, Meera M.
4 Brüggemann-Klein, Anne
4 Cherubini, Alessandra
4 Cienciala, Luděk
4 Ciencialová, Lucie
4 Cremers, Armin B.
4 Danicic, Sebastian
4 Finkel, Olivier
4 Frisco, Pierluigi
4 Gurari, Eitan M.
4 Harju, Tero
4 Harrison, Michael A.
4 Hierons, Robert Mark
4 Hotz, Günter
4 Igarashi, Yoshihide
4 Jirásek, Jozef jun.
4 Laurence, Michael R.
4 Leone, Nicola
4 Lohrey, Markus
4 Miyano, Satoru
4 Mrykhin, Mikhail
4 Nyberg-Brodda, Carl-Fredrik
4 Petersen, Holger
4 Rosenkrantz, Daniel J.
4 Say, A. C. Cem
4 Siromoney, Rani
4 Tucker, John V.
4 Woodworth, Sara
4 Yamakami, Tomoyuki
4 Yehudai, Amiram
4 Yokomori, Takashi
3 Alhazov, Artiom
3 Birget, Jean-Camille
3 Brandstädt, Andreas
3 Choffrut, Christian
3 Czerwiński, Wojciech
3 Dikovsky, Alexander Yakovlevich
3 Duske, Jürgen
3 Elder, Murray J.
3 Eremondi, Joey
3 Frougny, Christiane
...and 562 more Authors
all top 5

Cited in 80 Serials

193 Theoretical Computer Science
124 Journal of Computer and System Sciences
53 Mathematical Systems Theory
47 Information Processing Letters
40 Acta Informatica
39 Information and Computation
36 International Journal of Foundations of Computer Science
29 RAIRO, Informatique Théorique
21 Information Sciences
17 International Journal of Computer Mathematics
10 Theory of Computing Systems
8 RAIRO. Informatique Théorique et Applications
7 International Journal of Computer & Information Sciences
6 Discrete Mathematics
5 Discrete Applied Mathematics
5 Journal of Soviet Mathematics
5 Kybernetika
5 RAIRO. Theoretical Informatics and Applications
4 RAIRO. Theoretical Informatics and Applications
4 Natural Computing
3 Archiv für Mathematische Logik und Grundlagenforschung
3 Czechoslovak Mathematical Journal
3 Journal of Algebra
3 Annals of Pure and Applied Logic
3 International Journal of Algebra and Computation
3 Cybernetics and Systems Analysis
3 Journal of Logic, Language and Information
3 The Journal of Logic and Algebraic Programming
3 BIT. Nordisk Tidskrift for Informationsbehandling
3 Journal of Logical and Algebraic Methods in Programming
2 Communications in Algebra
2 Calcolo
2 Computing
2 Publications of the Research Institute for Mathematical Sciences, Kyoto University
2 Studia Logica
2 Cybernetics
2 New Generation Computing
2 Algorithmica
2 Applicable Algebra in Engineering, Communication and Computing
2 Fundamenta Informaticae
2 Logical Methods in Computer Science
2 Revue Française d’Automatique, Informatique, Recherche Opérationnelle. Série Rouge
2 Computer Science Review
1 International Journal of General Systems
1 Israel Journal of Mathematics
1 Moscow University Mathematics Bulletin
1 Problems of Information Transmission
1 Algebra and Logic
1 Annales de l’Institut Fourier
1 BIT
1 Mathematische Zeitschrift
1 Proceedings of the American Mathematical Society
1 Semigroup Forum
1 Transactions of the American Mathematical Society
1 Advances in Applied Mathematics
1 Acta Applicandae Mathematicae
1 Journal of Automated Reasoning
1 Applied Mathematics Letters
1 Mathematical and Computer Modelling
1 Computational Geometry
1 Discrete Mathematics and Applications
1 Mémoires de la Société Mathématique de France. Nouvelle Série
1 Indagationes Mathematicae. New Series
1 Russian Mathematics
1 Formal Methods in System Design
1 Journal of Functional Programming
1 Annals of Mathematics and Artificial Intelligence
1 Computer Science Journal of Moldova
1 Discrete Mathematics and Theoretical Computer Science. DMTCS
1 Journal of the Australian Mathematical Society
1 Journal of Applied Mathematics
1 ACM Transactions on Computational Logic
1 Journal of Applied Logic
1 Proceedings of the Steklov Institute of Mathematics
1 Groups, Complexity, Cryptology
1 The Review of Symbolic Logic
1 ISRN Algebra
1 Journal of Applied Mathematics, Statistics and Informatics
1 Modelirovanie i Analiz Informatsionnykh Sistem
1 Journal of Membrane Computing

Citations by Year