Edit Profile (opens in new tab) Greibach, Sheila A. Compute Distance To: Compute Author ID: greibach.sheila-a Published as: Greibach, S. A.; Greibach, Sheila A.; Greibach, S.; Greibach, Sheila; Greibach, Sh. A. more...less Documents Indexed: 75 Publications since 1963, including 3 Books Co-Authors: 16 Co-Authors with 37 Joint Publications 404 Co-Co-Authors all top 5 Co-Authors 38 single-authored 13 Ginsburg, Seymour 9 Book, Ronald Vernon 5 Friedman, Emily P. 4 Hopcroft, John Edward H. 3 Carlyle, Jack W. 3 Paz, Azaria 3 Wrathall, Celia 2 Even, Shimon 2 Goldstine, Jonathan 2 Harrison, Michael A. 2 Ott, Gene 2 Rolim, José D. P. 2 Wegbreit, Ben 1 Ibarra, Oscar H. 1 Shi, Weiping 1 Simonson, Shai all top 5 Serials 13 Journal of Computer and System Sciences 10 Information and Control 7 Journal of the Association for Computing Machinery 4 Mathematical Systems Theory 4 RAIRO, Informatique Théorique 4 Theoretical Computer Science 3 Information Processing Letters 3 SIAM Journal on Computing 2 IEEE Transactions on Computers 2 Lecture Notes in Computer Science 1 Acta Informatica 1 Annals of the History of Computing 1 Discrete Mathematics 1 International Journal of Computer & Information Sciences 1 Kiberneticheskiĭ Sbornik. Novaya Seriya 1 Memoirs of the American Mathematical Society 1 Proceedings of the American Mathematical Society 1 Communications of the ACM 1 RAIRO. Informatique Théorique et Applications all top 5 Fields 58 Computer science (68-XX) 11 Mathematical logic and foundations (03-XX) 2 Biology and other natural sciences (92-XX) 1 History and biography (01-XX) 1 Combinatorics (05-XX) 1 Information and communication theory, circuits (94-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 65 Publications have been cited 1,387 times in 794 Documents Cited by ▼ Year ▼ Remarks on blind and partially blind one-way multicounter machines. Zbl 0389.68030Greibach, S. A. 91 1978 One-way stack automata. Zbl 0171.14803Ginsburg, Seymour; Greibach, Sheila A.; Harrison, Michael A. 82 1967 Deterministic context free languages. Zbl 0145.00802Ginsburg, S.; Greibach, S. 80 1966 Studies in abstract families of languages. Zbl 0194.31402Ginsburg, Seymour; Greibach, Sheila; Hopcroft, John 63 1969 A new normal-form theorem for context-free phrase structure grammars. Zbl 0135.18404Greibach, S. A. 59 1965 The hardest context-free language. Zbl 0278.68073Greibach, Sheila A. 58 1973 Checking automata and one-way stack languages. Zbl 0174.02702Greibach, S. 55 1969 Principal AFL. Zbl 0198.03102Ginsburg, S.; Greibach, S. 53 1970 Scattered context grammars. Zbl 0174.02801Greibach, S.; Hopcroft, J. 52 1969 An infinite hierarchy of context-free languages. Zbl 0182.02002Greibach, S. A. 51 1969 Quasi-real-time languages. Zbl 0188.33102Book, R. V.; Greibach, S. A. 50 1970 Theory of program structures: Schemes, semantics, verification. Zbl 0345.68002Greibach, Sheila A. 42 1975 Full AFLs and nested iterated substitution. Zbl 0188.03102Greibach, S. A. 41 1970 Chains of full AFL’s. Zbl 0203.30102Greibach, S. A. 40 1970 Stack automata and compiling. Zbl 0153.01101Ginsburg, Seymour; Greibach, Sheila A.; Harrison, Michael A. 36 1967 Abstract families of languages. Zbl 0308.68058Ginsburg, S.; Greibach, S. 33 1975 One way finite visit automata. Zbl 0368.68059Greibach, S. A. 32 1978 Remarks on the complexity of nondeterministic counter languages. Zbl 0332.68039Greibach, S. A. 28 1976 The unsolvability of the recognition of linear context-free languages. Zbl 0148.00901Greibach, Sheila A. 27 1966 Syntactic operators on full semiAFLs. Zbl 0269.68046Greibach, Sheila A. 26 1972 A note on undecidable properties of formal languages. Zbl 0157.01902Greibach, S. 25 1968 Ambiguity in graphs and expressions. Zbl 0222.94067Book, Ronald; Even, Shimon; Greibach, Sheila; Ott, Gene 24 1971 Time- and tape-bounded Turing acceptors and AFLs. Zbl 0206.28702Book, R. V.; Greibach, S. A.; Wegbreit, B. 22 1970 Control sets on context-free grammar forms. Zbl 0359.68093Greibach, S. A. 20 1977 Reset machines. Zbl 0427.03029Book, Ronald V.; Greibach, Sheila A.; Wrathall, Celia 19 1979 Superdeterministic PDAs: A subcase with a decidable inclusion problem. Zbl 0462.68030Greibach, S. A.; Friedman, E. P. 18 1980 Mappings which preserve context sensitive languages. Zbl 0145.00803Ginsburg, S.; Greibach, S. A. 18 1966 A note on pushdown store automata and regular systems. Zbl 0183.01703Greibach, S. A. 18 1967 One counter languages and the IRS condition. Zbl 0307.68062Greibach, S. A. 17 1975 Jump PDA’s and hierarchies of deterministic context-free languages. Zbl 0288.68031Greibach, S. A. 17 1974 Erasable context-free languages. Zbl 0317.68059Greibach, S. A. 16 1975 The undecidability of the ambiguity problem for minimal linear grammars. Zbl 0115.37007Greibach, Sh. A. 14 1963 Multitape AFA. Zbl 0241.68031Greibach, Sheila; Ginsburg, Seymour 14 1972 Superdeterministic DPDAs: The method of accepting does affect decision problems. Zbl 0419.68100Friedman, E. P.; Greibach, S. A. 12 1979 Some uniformly erasable families of languages. Zbl 0343.68033Ginsburg, Seymour; Goldstine, Jonathan; Greibach, Sheila 11 1976 Erasing in context-free AFLs. Zbl 0248.68036Greibach, S. A. 10 1972 Uniformly erasable AFL. Zbl 0325.68042Ginsburg, Seymour; Goldstine, Jonathan; Greibach, Sheila 10 1975 Visits, crosses, and reversals for nondeterministic off-line machines. Zbl 0375.02027Greibach, S. A. 9 1978 A polynomial time algorithm for deciding the equivalence problem for 2- tape deterministic finite state acceptors. Zbl 0497.68050Friedman, E. P.; Greibach, S. A. 8 1982 Tape-bounded Turing acceptors and principal AFLs. Zbl 0206.28703Book, R. V.; Greibach, S. A.; Ibarra, O. H.; Wegbreit, B. 8 1970 Hierarchy theorems for two-way finite state transducers. Zbl 0398.68038Greibach, S. A. 8 1978 On AFL generators for finitely encoded AFA. Zbl 0249.68025Ginsburg, Seymour; Greibach, Sheila 7 1973 Linearity is polynomially decidable for realtime pushdown store automata. Zbl 0413.68086Greibach, S. A. 7 1979 Characteristic and ultrarealtime languages. Zbl 0216.23803Greibach, S. A. 6 1971 A generalization of Parikh’s semilinear theorem. Zbl 0251.68043Greibach, S. A. 6 1972 One counter languages and the Chevron operation. Zbl 0441.68081Greibach, S. A. 4 1979 The independence of certain operations on semi-AFLs. Zbl 0388.68068Book, Ronald V.; Greibach, Sheila A. 4 1978 Some restrictions on W-grammars. Zbl 0288.68035Greibach, Sheila A. 4 1974 Single tree grammars. Zbl 0765.68071Greibach, Sheila; Shi, Weiping; Simonson, Shai 3 1992 The strong independence of substitution and homomorphic replication. Zbl 0387.68048Greibach, S. A. 3 1978 Comments on universal and left universal grammars, context-sensitive languages, and context-free grammar forms. Zbl 0387.68059Greibach, S. A. 3 1978 On equivalence and subclass containment problems for deterministic context-free languages. Zbl 0392.68069Friedman, E. P.; Greibach, S. A. 3 1978 A remark on code sets and context-free languages. Zbl 0307.68058Greibach, S. A. 3 1975 A note on the best-case complexity. Zbl 0672.68019Rolim, José D. P.; Greibach, Sheila A. 2 1989 Comparisons and reset machines. Zbl 0388.03017Book, Ronald V.; Greibach, Sheila A.; Wrathall, Celia 2 1978 Monadic recursion schemes: The effect of constants. Zbl 0411.03010Friedman, Emily P.; Greibach, Sheila A. 2 1979 Ambiguity in graphs and expressions. Zbl 0294.94028Book, R.; Even, S.; Greibach, S.; Ott, G. 2 1969 Principal AFL. Zbl 0308.68059Ginsburg, S.; Greibach, S. 2 1975 On the IO-complexity and approximation languages. Zbl 0659.03023Rolim, José D. P.; Greibach, Sheila A. 1 1988 Single-tape reset machines. Zbl 0585.68073Greibach, S. A.; Wrathall, C. 1 1986 Formal parsing systems. Zbl 0123.12602Greibach, Sheila A. 1 1964 Matching and spanning in certain planar graphs. Zbl 0527.05053Carlyle, J. W.; Greibach, S. A.; Paz, A. 1 1983 Formal languages: origins and directions. Zbl 0998.01515Greibach, S. A. 1 1981 A note on undecidable properties of formal languages. Zbl 0307.68055Greibach, S. 1 1975 Quasi-realtime languages (extended abstract). Zbl 1282.68152Book, Ronald V.; Greibach, Sheila A. 1 1969 Single tree grammars. Zbl 0765.68071Greibach, Sheila; Shi, Weiping; Simonson, Shai 3 1992 A note on the best-case complexity. Zbl 0672.68019Rolim, José D. P.; Greibach, Sheila A. 2 1989 On the IO-complexity and approximation languages. Zbl 0659.03023Rolim, José D. P.; Greibach, Sheila A. 1 1988 Single-tape reset machines. Zbl 0585.68073Greibach, S. A.; Wrathall, C. 1 1986 Matching and spanning in certain planar graphs. Zbl 0527.05053Carlyle, 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.68050Friedman, E. P.; Greibach, S. A. 8 1982 Formal languages: origins and directions. Zbl 0998.01515Greibach, S. A. 1 1981 Superdeterministic PDAs: A subcase with a decidable inclusion problem. Zbl 0462.68030Greibach, S. A.; Friedman, E. P. 18 1980 Reset machines. Zbl 0427.03029Book, Ronald V.; Greibach, Sheila A.; Wrathall, Celia 19 1979 Superdeterministic DPDAs: The method of accepting does affect decision problems. Zbl 0419.68100Friedman, E. P.; Greibach, S. A. 12 1979 Linearity is polynomially decidable for realtime pushdown store automata. Zbl 0413.68086Greibach, S. A. 7 1979 One counter languages and the Chevron operation. Zbl 0441.68081Greibach, S. A. 4 1979 Monadic recursion schemes: The effect of constants. Zbl 0411.03010Friedman, Emily P.; Greibach, Sheila A. 2 1979 Remarks on blind and partially blind one-way multicounter machines. Zbl 0389.68030Greibach, S. A. 91 1978 One way finite visit automata. Zbl 0368.68059Greibach, S. A. 32 1978 Visits, crosses, and reversals for nondeterministic off-line machines. Zbl 0375.02027Greibach, S. A. 9 1978 Hierarchy theorems for two-way finite state transducers. Zbl 0398.68038Greibach, S. A. 8 1978 The independence of certain operations on semi-AFLs. Zbl 0388.68068Book, Ronald V.; Greibach, Sheila A. 4 1978 The strong independence of substitution and homomorphic replication. Zbl 0387.68048Greibach, S. A. 3 1978 Comments on universal and left universal grammars, context-sensitive languages, and context-free grammar forms. Zbl 0387.68059Greibach, S. A. 3 1978 On equivalence and subclass containment problems for deterministic context-free languages. Zbl 0392.68069Friedman, E. P.; Greibach, S. A. 3 1978 Comparisons and reset machines. Zbl 0388.03017Book, Ronald V.; Greibach, Sheila A.; Wrathall, Celia 2 1978 Control sets on context-free grammar forms. Zbl 0359.68093Greibach, S. A. 20 1977 Remarks on the complexity of nondeterministic counter languages. Zbl 0332.68039Greibach, S. A. 28 1976 Some uniformly erasable families of languages. Zbl 0343.68033Ginsburg, Seymour; Goldstine, Jonathan; Greibach, Sheila 11 1976 Theory of program structures: Schemes, semantics, verification. Zbl 0345.68002Greibach, Sheila A. 42 1975 Abstract families of languages. Zbl 0308.68058Ginsburg, S.; Greibach, S. 33 1975 One counter languages and the IRS condition. Zbl 0307.68062Greibach, S. A. 17 1975 Erasable context-free languages. Zbl 0317.68059Greibach, S. A. 16 1975 Uniformly erasable AFL. Zbl 0325.68042Ginsburg, Seymour; Goldstine, Jonathan; Greibach, Sheila 10 1975 A remark on code sets and context-free languages. Zbl 0307.68058Greibach, S. A. 3 1975 Principal AFL. Zbl 0308.68059Ginsburg, S.; Greibach, S. 2 1975 A note on undecidable properties of formal languages. Zbl 0307.68055Greibach, S. 1 1975 Jump PDA’s and hierarchies of deterministic context-free languages. Zbl 0288.68031Greibach, S. A. 17 1974 Some restrictions on W-grammars. Zbl 0288.68035Greibach, Sheila A. 4 1974 The hardest context-free language. Zbl 0278.68073Greibach, Sheila A. 58 1973 On AFL generators for finitely encoded AFA. Zbl 0249.68025Ginsburg, Seymour; Greibach, Sheila 7 1973 Syntactic operators on full semiAFLs. Zbl 0269.68046Greibach, Sheila A. 26 1972 Multitape AFA. Zbl 0241.68031Greibach, Sheila; Ginsburg, Seymour 14 1972 Erasing in context-free AFLs. Zbl 0248.68036Greibach, S. A. 10 1972 A generalization of Parikh’s semilinear theorem. Zbl 0251.68043Greibach, S. A. 6 1972 Ambiguity in graphs and expressions. Zbl 0222.94067Book, Ronald; Even, Shimon; Greibach, Sheila; Ott, Gene 24 1971 Characteristic and ultrarealtime languages. Zbl 0216.23803Greibach, S. A. 6 1971 Principal AFL. Zbl 0198.03102Ginsburg, S.; Greibach, S. 53 1970 Quasi-real-time languages. Zbl 0188.33102Book, R. V.; Greibach, S. A. 50 1970 Full AFLs and nested iterated substitution. Zbl 0188.03102Greibach, S. A. 41 1970 Chains of full AFL’s. Zbl 0203.30102Greibach, S. A. 40 1970 Time- and tape-bounded Turing acceptors and AFLs. Zbl 0206.28702Book, R. V.; Greibach, S. A.; Wegbreit, B. 22 1970 Tape-bounded Turing acceptors and principal AFLs. Zbl 0206.28703Book, R. V.; Greibach, S. A.; Ibarra, O. H.; Wegbreit, B. 8 1970 Studies in abstract families of languages. Zbl 0194.31402Ginsburg, Seymour; Greibach, Sheila; Hopcroft, John 63 1969 Checking automata and one-way stack languages. Zbl 0174.02702Greibach, S. 55 1969 Scattered context grammars. Zbl 0174.02801Greibach, S.; Hopcroft, J. 52 1969 An infinite hierarchy of context-free languages. Zbl 0182.02002Greibach, S. A. 51 1969 Ambiguity in graphs and expressions. Zbl 0294.94028Book, R.; Even, S.; Greibach, S.; Ott, G. 2 1969 Quasi-realtime languages (extended abstract). Zbl 1282.68152Book, Ronald V.; Greibach, Sheila A. 1 1969 A note on undecidable properties of formal languages. Zbl 0157.01902Greibach, S. 25 1968 One-way stack automata. Zbl 0171.14803Ginsburg, Seymour; Greibach, Sheila A.; Harrison, Michael A. 82 1967 Stack automata and compiling. Zbl 0153.01101Ginsburg, Seymour; Greibach, Sheila A.; Harrison, Michael A. 36 1967 A note on pushdown store automata and regular systems. Zbl 0183.01703Greibach, S. A. 18 1967 Deterministic context free languages. Zbl 0145.00802Ginsburg, S.; Greibach, S. 80 1966 The unsolvability of the recognition of linear context-free languages. Zbl 0148.00901Greibach, Sheila A. 27 1966 Mappings which preserve context sensitive languages. Zbl 0145.00803Ginsburg, S.; Greibach, S. A. 18 1966 A new normal-form theorem for context-free phrase structure grammars. Zbl 0135.18404Greibach, S. A. 59 1965 Formal parsing systems. Zbl 0123.12602Greibach, Sheila A. 1 1964 The undecidability of the ambiguity problem for minimal linear grammars. Zbl 0115.37007Greibach, Sh. A. 14 1963 all cited Publications top 5 cited Publications all top 5 Cited by 637 Authors 47 Ibarra, Oscar H. 30 Greibach, Sheila A. 25 Kutrib, Martin 22 Engelfriet, Joost 19 Book, Ronald Vernon 17 McQuillan, Ian 16 Ginsburg, Seymour 16 Rozenberg, Grzegorz 14 Meduna, Alexander 14 Okhotin, Alexander 13 Boasson, Luc 13 Latteux, Michel 12 Beauquier, Joffroy 10 Autebert, Jean-Michel 10 Goldstine, Jonathan 10 Inoue, Katsushi 10 Malcher, Andreas 10 Sénizergues, Géraud 9 Fernau, Henning 9 Vogler, Heiko 8 Holzer, Markus 8 Hromkovič, Juraj 8 Jantzen, Matthias 8 Otto, Friedrich 8 Păun, Gheorghe 8 Ravikumar, Bala 8 Wood, Derick 7 Brandenburg, Franz-Josef 7 Salomaa, Kai T. 7 Takanami, Itsuo 7 Wotschke, Detlef 7 Wrathall, Celia 7 Zetzsche, Georg 6 Ehrenfeucht, Andrzej 6 Friedman, Emily P. 6 Hopcroft, John Edward H. 6 Hunt, Harry Bowen III 6 Karhumaki, Juhani 6 Slutzki, Giora 6 Spanier, Edwin Henry 6 Ullman, Jeffrey David 6 Wendlandt, Matthias 5 Bergstra, Jan A. 5 Crespi Reghizzi, Stefano 5 Culik, Karel II 5 D’Alessandro, Flavio 5 Gallier, Jean H. 5 Mitrana, Victor 5 Nivat, Maurice 5 Scarcello, Francesco 5 Turakainen, Paavo 4 Aho, Alfred Vaino 4 Asveld, Peter R. J. 4 Bordihn, Henning 4 Brüggemann-Klein, Anne 4 Cherubini, Alessandra 4 Cremers, Armin B. 4 Finkel, Olivier 4 Gurari, Eitan M. 4 Harju, Tero 4 Harrison, Michael A. 4 Hotz, Günter 4 Igarashi, Yoshihide 4 Kambites, Mark 4 Leone, Nicola 4 Lohrey, Markus 4 McKenzie, Pierre 4 Miyano, Satoru 4 Petersen, Holger 4 Rosenkrantz, Daniel J. 4 Say, A. C. Cem 4 Siromoney, Rani 4 Tucker, John V. 4 Woodworth, Sara 4 Yehudai, Amiram 4 Yokomori, Takashi 3 Alhazov, Artiom 3 Bensch, Suna 3 Bhaskar, Siddharth 3 Birget, Jean-Camille 3 Blattner, Meera M. 3 Brandstädt, Andreas 3 Choffrut, Christian 3 Cienciala, Luděk 3 Ciencialová, Lucie 3 Danicic, Sebastian 3 Dikovsky, Alexander Yakovlevich 3 Duske, Jürgen 3 Elder, Murray J. 3 Eremondi, Joey 3 Frisco, Pierluigi 3 Frougny, Christiane 3 Gottlob, Georg 3 Gruska, Jozef 3 Hashiguchi, Kosaburo 3 Haussler, David 3 Havel, Ivan M. 3 Hofbauer, Dieter 3 Honda, Namio 3 Hoogeboom, Hendrik Jan ...and 537 more Authors all top 5 Cited in 77 Serials 190 Theoretical Computer Science 123 Journal of Computer and System Sciences 53 Mathematical Systems Theory 47 Information Processing Letters 39 Acta Informatica 37 Information and Computation 30 International Journal of Foundations of Computer Science 29 RAIRO, Informatique Théorique 21 Information Sciences 17 International Journal of Computer Mathematics 8 RAIRO. Informatique Théorique et Applications 8 Theory of Computing Systems 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 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 Calcolo 2 Computing 2 Journal of Algebra 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 Revue Française d’Automatique, Informatique, Recherche Opérationnelle. Série Rouge 2 Computer Science Review 1 Communications in Algebra 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 Annals of Mathematics and Artificial Intelligence 1 Discrete Mathematics and Theoretical Computer Science. DMTCS 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 Logical Methods in Computer Science 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 all top 5 Cited in 20 Fields 756 Computer science (68-XX) 113 Mathematical logic and foundations (03-XX) 24 Group theory and generalizations (20-XX) 8 Combinatorics (05-XX) 4 Number theory (11-XX) 4 Biology and other natural sciences (92-XX) 4 Information and communication theory, circuits (94-XX) 3 Associative rings and algebras (16-XX) 3 Category theory; homological algebra (18-XX) 2 Measure and integration (28-XX) 2 Quantum theory (81-XX) 2 Operations research, mathematical programming (90-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 General algebraic systems (08-XX) 1 Topological groups, Lie groups (22-XX) 1 Geometry (51-XX) 1 Convex and discrete geometry (52-XX) 1 Numerical analysis (65-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Systems theory; control (93-XX) Citations by Year