Adding symbolic information to picture models: definitions and properties. (English) Zbl 1077.68041

Summary: We propose extensions of some picture models, such as colored, drawn and pixel pictures. Such extensions are conceived by observing that a picture may embed more information than the shape, such as colors, labels, etc., which can be represented by a symbol from an alphabet and can be associated to segments, points or pixels. New interesting issues derived from the introduction of symbols will be investigated together with some complexity and decidability questions for the proposed extensions.


68Q45 Formal languages and automata
03B25 Decidability of theories and sets of sentences
Full Text: DOI


[1] Berstel, J., Transductions and context-free languages, (1979), Teubner Studienbücher Stuttgart · Zbl 0424.68040
[2] F.J. Brandenburg, On Minimal Picture Words, MIP 8903, Tech. Report, University of Passau, 1989.
[3] Brandenburg, F.J.; Dassow, J., Reduction of picture words, Rairo tcs, 27, 49-56, (1993) · Zbl 0770.68081
[4] K. Culik, E. Welzl, Two finite state generator, Lecture Notes on Computer Science, Vol. 158, Springer, Berlin, 1983, 1997, pp. 106-114.
[5] Dassow, J.; Hinz, F., Decision problems and regular chain code picture languages, Discrete math., 45, 29-49, (1993) · Zbl 0797.68096
[6] Ginsburg, S., The mathematical theory of context-free languages, (1966), McGraw-Hill New York · Zbl 0184.28401
[7] F. Hinz, Questions of decidability for context-free chain code picture languages, in: Proc. IMYCS’88, Hungarian Academy of Sciences, 1988.
[8] F. Hinz, E. Welzl, Regular chain code picture languages with invisible lines, Tech. Report 252, IIG, Tech. Univ. Graz, Austria, 1988.
[9] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[10] Kim, C., Picture iteration and picture ambiguity, J. comput. system sci., 40, 289-306, (1990) · Zbl 0694.68053
[11] Kim, C., Complexity and decidability for restricted class of picture languages, Theoret. comput. sci., 73, 295-311, (1990) · Zbl 0694.68052
[12] Kim, C., Retrat bounded picture languages, Theoret. comput. sci., 132, 85-112, (1994) · Zbl 0938.68708
[13] Kim, C.; Sudborough, I.H., The membership and equivalence problems for picture languages, Theoret. comput. sci., 52, 177-191, (1987) · Zbl 0636.68117
[14] Kim, C.; Sudborough, I.H., On reversal bounded picture languages, Theoret. comput. sci., 104, 185-206, (1992) · Zbl 0754.68068
[15] Latteux, M.; Robilliard, D.; Simplot, D., Figures composés de pixels et monoide inversif, Bull. Belgian math. soc., 4, 89-111, (1997) · Zbl 0917.68121
[16] Maurer, H.A.; Rozenberg, G.; Welzl, E., Using string languages to describe picture languages, Inform. control, 54, 155-185, (1982) · Zbl 0523.68065
[17] Pelletier, M.; Sakarovitch, J., Easy multiplication II—extensions of rational semigroups, Inform. comput., 88, 18-59, (1990) · Zbl 0705.20057
[18] Petrich, M., Inverse semigroups, (1984), Wiley New York · Zbl 0546.20053
[19] Robilliard, D.; Simplot, D., Undecidability of existential properties in picture languages, Theoret. comput. sci., 233, 51-74, (2000) · Zbl 0952.68083
[20] Sakarovitch, J., Description des monoides de type fini, J. inform. process. cybernet., 17, 8, 417-434, (1981) · Zbl 0572.20037
[21] Salomaa, A., Formal languages, (1973), Academic Press London · Zbl 0262.68025
[22] Sudborough, I.H.; Welzl, E., Complexity and decidability for chain code picture languages, Theoret. comput. sci., 36, 173-202, (1985) · Zbl 0565.68065
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.