×

Concise description of finite languages. (English) Zbl 0469.68081


MSC:

68Q45 Formal languages and automata
PDF BibTeX XML Cite
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 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, (), 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, (), 54-65
[11] Kintala, Ch.M.R.; Wotschke, D., Succinctness of degree automata and probabilistic automata, Proc. allerton conference, (1978)
[12] Ch.M.R. Kintala and D. Wotschke, Amounts of nondeterminism in finite automata, to appear. · Zbl 0423.68016
[13] Maurer, H., Theoretische grundlagen der programmiersprachen-theorie der syntax, (1969), 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, (), 344-350 · Zbl 0318.68049
[16] Pirická, A., Complexity and normal forms of context-free languages, (), 292-297 · Zbl 0312.68038
[17] Price, J.K.; Wotschke, D., States can sometimes do more than stack symbols in PDA’s, (), 353-362 · Zbl 0381.68054
[18] Salomaa, A., Formal languages, (1973), 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, ()
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.