×
Bucher, W.; Maurer, H. A.; Čulik, Karel II; Wotschke, D.

Concise description of finite languages. (English) Zbl 0469.68081

Theor. Comput. Sci. 14, 227-246 (1981).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0469.68081

Cited in 1 Review
Cited in 17 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

grammatical complexity
PDF BibTeX XML Cite
\textit{W. Bucher} et al., Theor. Comput. Sci. 14, 227--246 (1981; Zbl 0469.68081)
Full Text: DOI

References:

[1] Blum, M., On the size of machines, Information and Control, 11, 257-265 (1967) · Zbl 0165.02102
[2] Cremers, A. B., Die Konstruktionskomplexität context-freier Sprachen, Ph.D. Thesis Universität Karlsruhe (1972)
[3] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[4] Ginsburg, S.; Lynch, N., Size complexity in context-free grammar forms, J. ACM, 23, 582-598 (1976) · Zbl 0333.68057
[5] Gruska, J., On a classification of context-free languages, Kybernetica, 3, 22-29 (1967) · Zbl 0158.25401
[6] Gruska, J., Some classifications of context-free languages, Information and Control, 14, 152-179 (1969) · Zbl 0174.28901
[7] Gruska, J., Complexity and unambiguity of context-free languages, Information and Control, 18, 502-519 (1971) · Zbl 0238.68022
[8] Hartmanis, J., On the succinctness of different representations of languages, (Proc. 6th ICALP (1979), Springer: Springer Berlin), Lecture Notes in Computer Science · Zbl 0412.68076
[9] Hartmanis, J., Relative succinctness of representations of languages and separation of complexity classes, Cornell University Computer Science Report TR 78-349 (1978)
[10] Hunt, H. B.; Szymanski, T. G., On the complexity of grammar and related problems, (Proc. 7th STOC (1975), ACM: ACM New York), 54-65 · Zbl 0361.68078
[11] Kintala, Ch. M.R.; Wotschke, D., Succinctness of degree automata and probabilistic automata, Proc. Allerton Conference (1978)
[13] Maurer, H., Theoretische Grundlagen der Programmiersprachen-Theorie der Syntax (1969), BI: BI Mannheim · Zbl 0204.31801
[14] Meyer, A. R.; Fischer, M. J., Economy of description by automata, grammars and formal systems, IEEE 12th Annual Symposium on Switching and Automata Theory, 188-190 (1971)
[15] Pirická-Kelemenová, A., Greibach normal form complexity, (Proc. MFCS 75. Proc. MFCS 75, Lecture Notes in Computer Science, 32 (1975), Springer: Springer Berlin), 344-350 · Zbl 0318.68049
[16] Pirická, A., Complexity and normal forms of context-free languages, (Proc. MFCS 74. Proc. MFCS 74, Lecture Notes in Computer Science, 28 (1974), Springer: Springer Berlin), 292-297 · Zbl 0312.68038
[17] Price, J. K.; Wotschke, D., States can sometimes do more than stack symbols in PDA’s, (Proc. 5th ICALP. Proc. 5th ICALP, Lecture Notes in Computer Science, 62 (1978), Springer: Springer Berlin), 353-362 · Zbl 0381.68054
[18] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025
[19] Schmidt, E. M.; Szymanski, T. G., Succinctness of description of unambigous context-free languages, SIAM J. Comput., 6, 547-553 (1977) · Zbl 0357.68088
[20] Valiant, L. G., A note on the succinctness of descriptions of deterministic languages, Information and Control, 32, 139-145 (1976) · Zbl 0338.68059
[21] Wegner, L., Analysis of two-level grammars, (Informatik, 1 (1978), Hochschulverlag: Hochschulverlag Stuttgart)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.