Sheila A. Greibach

According to our database1, Sheila A. Greibach
  • authored at least 76 papers between 1963 and 2005.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2005
In memory of Seymour Ginsburg 1928 - 2004.
SIGMOD Record, 2005

1992
Single Tree Grammars.
Proceedings of the Theoretical Studies in Computer Science, 1992

1989
A Note on the Best-Case Complexity.
Inf. Process. Lett., 1989

1988
On the IO-Complexity and Approximation Languages.
Inf. Process. Lett., 1988

1986
Single-Tape Reset Machines.
ITA, 1986

Complexity of pattern generation via planar parallel binary fission/fusion grammars.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1986

1983
Matching and Spanning in Certain Planar Graphs.
Mathematical Systems Theory, 1983

1982
A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors.
SIAM J. Comput., 1982

1981
Formal Languages: Origins and Directions.
IEEE Annals of the History of Computing, 1981

1980
Superdeterministic PDAs: A Subcase with a Decidable Inclusion problem.
J. ACM, 1980

1979
Linearity is Polynomially Decidable for Realtime Pushdown Store Automatia
Information and Control, July, 1979

Superdeterministic DPDAS: The Method for Accepting Does Affect Decision Problems.
J. Comput. Syst. Sci., 1979

Monadic Recursion Schemes: The Effect of Constants.
J. Comput. Syst. Sci., 1979

Reset Machines.
J. Comput. Syst. Sci., 1979

One counter languages and the chevron operation.
ITA, 1979

Formal Languages: Origins and Directions
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
Comments on Universal and Left Universal Grammars, Context-Sensitive Languages, and Context-Free Grammar Forms
Information and Control, November, 1978

Visits, Crosses, and Reversals for Nondeterministic Off-Line Machines
Information and Control, February, 1978

Remarks on Blind and Partially Blind One-Way Multicounter Machines.
Theor. Comput. Sci., 1978

One Way Finite Visit Automata.
Theor. Comput. Sci., 1978

The strong independence of substitution and homomorphic replication.
ITA, 1978

The Independence of Certain Operations on semiAFLS.
ITA, 1978

On Equivalence and Subclass Containment Problems for Deterministic Context-Free Languages.
Inf. Process. Lett., 1978

Hierarchy Theorems for Two-Way Finite State Transducers.
Acta Inf., 1978

Comparisons and Reset Machines (Preliminary Report).
Proceedings of the Automata, 1978

1977
Control Sets of Context-Free Grammar Forms.
J. Comput. Syst. Sci., 1977

A Note on NSPACE(log2 n) and Substitution.
ITA, 1977

1976
Remarks on the Complexity of Nondeterministic Counter Languages.
Theor. Comput. Sci., 1976

Some Uniformly Erasable Families of Languages.
Theor. Comput. Sci., 1976

1975
Erasable Context-Free Languages
Information and Control, December, 1975

A Remark on Code Sets and Context-Free Languages.
IEEE Trans. Computers, 1975

One Counter Languages and the IRS Condition.
J. Comput. Syst. Sci., 1975

Uniformly Erasable AFL.
J. Comput. Syst. Sci., 1975

A Note on the Recognition of One Counter Languages.
ITA, 1975

Theory of Program Structures: Schemes, Semantics, Verification
Lecture Notes in Computer Science 36, Springer, ISBN: 3-540-07415-5, 1975

1974
Jump PDA's and Hierarchies of Deterministic Context-Free Languages.
SIAM J. Comput., 1974

Some restrictions onW-grammars.
International Journal of Parallel Programming, 1974

Some Restrictions on W-Grammars
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

A Two-Dimensional Generating System Modeling Growth by Binary Cell Division (Preliminary Report)
Proceedings of the 15th Annual Symposium on Switching and Automata Theory, 1974

1973
The Hardest Context-Free Language.
SIAM J. Comput., 1973

On AFL Generators for Finitely Encoded AFA.
J. Comput. Syst. Sci., 1973

Jump PDA's, Deterministic Context-Free Languages Principal AFDLs and Polynomial Time Recognition-Extended Abstract
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30, 1973

1972
Erasing in Context-Free AFLs
Information and Control, December, 1972

Syntactic Operators on Full SemiAFLs.
J. Comput. Syst. Sci., 1972

Multitape AFA.
J. ACM, 1972

A generalization of Parikh's semilinear theorem.
Discrete Mathematics, 1972

Uniformly Erasable AFL
Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972

1971
Characteristic and Ultrarealtime Languages
Information and Control, February, 1971

Ambiguity in Graphs and Expressions.
IEEE Trans. Computers, 1971

1970
Full AFLs and Nested Iterated Substitution
Information and Control, March, 1970

Chains of Full AFL's.
Mathematical Systems Theory, 1970

Quasi-Realtime Languages.
Mathematical Systems Theory, 1970

Principal AFL.
J. Comput. Syst. Sci., 1970

Time- and Tape-Bounded Turing Acceptors and AFLs.
J. Comput. Syst. Sci., 1970

Tape-Bounded Turing Acceptors and Principal AFLs.
J. Comput. Syst. Sci., 1970

Tape- and Time-Bounded Turing Acceptors and AFLs: Extended Abstract
Proceedings of the 2nd Annual ACM Symposium on Theory of Computing, 1970

1969
Scattered Context Grammars.
J. Comput. Syst. Sci., 1969

Checking Automata and One-Way Stack Languages.
J. Comput. Syst. Sci., 1969

An Infinite Hierarchy of Context-Free Languages.
J. ACM, 1969

Quasi-Realtime Languages-Extended Abstract
Proceedings of the 1st Annual ACM Symposium on Theory of Computing, 1969

Full AFLs and Nested Iterated Substitution
Proceedings of the 10th Annual Symposium on Switching and Automata Theory, 1969

1968
A Note on Undecidable Properties of Formal Languages.
Mathematical Systems Theory, 1968

Scattered context grammars.
IFIP Congress (1), 1968

Checking Automata and One-Way Stack Languages (Extended Abstract)
Proceedings of the 9th Annual Symposium on Switching and Automata Theory, 1968

1967
One-way stack automata.
J. ACM, 1967

Stack automata and compiling.
J. ACM, 1967

An Infinite Hierarchy of Context-Free Languages
Proceedings of the 8th Annual Symposium on Switching and Automata Theory, 1967

Abstract Families of Languages
Proceedings of the 8th Annual Symposium on Switching and Automata Theory, 1967

1966
Deterministic Context Free Languages
Information and Control, December, 1966

Mappings which Preserve Context Sensitive Languages
Information and Control, December, 1966

The Unsolvability of the Recognition of Linear Context-Free Languages.
J. ACM, 1966

One-Way Stack Automata (Extended Abstract)
Proceedings of the 7th Annual Symposium on Switching and Automata Theory, 1966

1965
A New Normal-Form Theorem for Context-Free Phrase Structure Grammars.
J. ACM, 1965

Deterministic context free languages
Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965

1964
Formal parsing systems.
Commun. ACM, 1964

1963
The Undecidability of the Ambiguity Problem for Minimal Linear Grammars
Information and Control, June, 1963


  Loading...