Abstract
The spider diagram logic forms a fragment of the constraint diagram logic and was designed to be primarily used as a diagrammatic software specification tool. Our interest is in using the logical basis of spider diagrams and the existing known equivalences between certain logics, formal language theory classes and some automata to inform the development of diagrammatic logics. Such developments could have many advantages, one of which would be aiding software engineers who are familiar with formal languages and automata to more intuitively understand diagrammatic logics. In this paper we consider relationships between spider diagrams of order (an extension of spider diagrams) and the star-free subset of regular languages. We extend the concept of the language of a spider diagram to encompass languages over arbitrary alphabets. Furthermore, the product of spider diagrams is introduced. This operator is the diagrammatic analogue of language concatenation. We establish that star-free languages are definable by spider diagrams of order equipped with the product operator and, based on this relationship, spider diagrams of order are as expressive as first order monadic logic of order.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barwise, J., Etchemendy, J.: Hyperproof. CSLI Press (1994)
Büchi, J.: Weak second order arithmetic and finite automata. Z. Math. Logik und Grundl. Math. 6, 66–92 (1960)
Chomsky, N.: Three models for the description of language. IRE Transactions on Information Theory, 113–124 (1956)
Delaney, A., Stapleton, G.: On the descriptional complexity of a diagrammatic notation. In: Visual Languages and Computing (September 2007)
Delaney, A., Stapleton, G.: Spider diagrams of order. In: International Workshop on Visual Languages and Logic (September 2007)
Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1991)
Euler, L.: Lettres a une princesse dallemagne sur divers sujets de physique et de philosophie. Letters 2, 102–108 (1775); Berne, Socit Typographique
Gil, J., Howse, J., Kent, S.: Formalising spider diagrams. In: Proceedings of IEEE Symposium on Visual Languages, Tokyo, September 1999, pp. 130–137. IEEE Computer Society Press, Los Alamitos (1999)
Hammer, E.: Logic and Visual Information. CSLI Publications (1995)
Héam, P.-C.: On shuffle ideals. Theoretical Informatics and Applications 36, 359–384 (2002)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing, Reading (1979)
Howse, J., Stapleton, G., Taylor, J.: Spider diagrams. LMS Journal of Computation and Mathematics 8, 145–194 (2005)
Kent, S.: Constraint diagrams: Visualizing invariants in object oriented modelling. In: Proceedings of OOPSLA 1997, October 1997, pp. 327–341. ACM Press, New York (1997)
Pin, J.-E.: Syntactic semigroups, pp. 679–746. Springer-Verlag, New York (1997)
Pin, J.-E., Straubing, H., Thérien, D.: Some results on the generalized star-height problem. Information and Computation 101, 219–250 (1992)
Shin, S.-J.: The Logical Status of Diagrams. Cambridge University Press, Cambridge (1994)
Stapleton, G., Thompson, S., Howse, J., Taylor, J.: The expressiveness of spider diagrams. Journal of Logic and Computation 14(6), 857–880 (2004)
Stern, J.: Characterizations of some classes of regular events. Theoretical Computer Science 35, 17–42 (1985)
Thomas, W.: Classifying regular events in symbolic logic. Journal of Computer and System Sciences 25, 360–376 (1982)
Venn, J.: On the diagrammatic and mechanical representation of propositions and reasonings. Phil. Mag. (1880)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Delaney, A., Taylor, J., Thompson, S. (2008). Spider Diagrams of Order and a Hierarchy of Star-Free Regular Languages. In: Stapleton, G., Howse, J., Lee, J. (eds) Diagrammatic Representation and Inference. Diagrams 2008. Lecture Notes in Computer Science(), vol 5223. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87730-1_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-87730-1_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87729-5
Online ISBN: 978-3-540-87730-1
eBook Packages: Computer ScienceComputer Science (R0)