Cited By
View all- Chapman PStapleton GDelaney A(2018)On the expressiveness of second-order spider diagramsJournal of Visual Languages and Computing10.1016/j.jvlc.2013.07.00224:5(327-349)Online publication date: 26-Dec-2018
On the expressiveness of spider diagrams and commutative star-free regular languages
Pages 273 - 288
Abstract
Spider diagrams provide a visual logic to express relations between sets and their elements, extending the expressiveness of Venn diagrams. Sound and complete inference systems for spider diagrams have been developed and it is known that they are equivalent in expressive power to monadic first-order logic with equality, MFOL=]. In this paper, we further characterize their expressiveness by articulating a link between them and formal languages. First, we establish that spider diagrams define precisely the languages that are finite unions of languages of the form K *, where K is a finite commutative language and is a finite set of letters. We note that it was previously established that spider diagrams define commutative star-free languages. As a corollary, all languages of the form K * are commutative star-free languages. We further demonstrate that every commutative star-free language is also such a finite union. In summary, we establish that spider diagrams define precisely: (a) languages definable in MFOL=], (b) the commutative star-free regular languages, and (c) finite unions of the form K *, as just described. Highlights We establish the expressiveness of spider diagrams with respect to formal languages. A characterisation of commutative star-free regular languages is also established. We show that spider diagrams define the commutative star-free regular languages.
References
[1]
Janusz A. Brzozowski, Hierarchies of aperiodic languages, RAIRO-Theoretical Informatics and Applications, 1976, pp. 33-49.
[2]
Richard Büchi, J., Weak second order arithmetic and finite automata. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik. v6 i1-6. 66-92.
[3]
Peter Chapman, Gem Stapleton, Introducing second order spider diagrams for defining regular languages, in: Proceedings of the Symposium on Visual Languages and Human-Centric Computing, IEEE, 2010, pp. 159-167.
[4]
Aidan Delaney, Gem Stapleton, Spider diagrams of order, in: Proceedings of the International Workshop on Visual Languages and Logic, vol. 274, CUER, September 2007, pp. 27-39.
[5]
Aidan Delaney, John Taylor, Simon Thompson, Spider diagrams of order and a hierarchy of star-free regular languages, in: Proceedings of the International Conference on the Theory and Application of Diagrams, Springer, 2008, pp. 172-187.
[6]
Eilenberg, Samuel, . 1974. Automata, Languages, and Machines, 1974.Academic Press Inc.
[7]
J. Gil, John Howse, S. Kent, Formalising spider diagrams, in: Symposium on Visual Languages, IEEE Computer Society Press, September 1999, pp. 130-137.
[8]
Higman, Graham, Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society. vs3-2 iJanuary (1). 326-336.
[9]
John E. Hopcroft. An nlogn algorithm for minimizing states in a finite automaton, Technical Report, Stanford, CA, USA, 1971.
[10]
Hopcroft, John E. and Karp, Richard M., An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing. v2 i4. 225-231.
[11]
Howse, John, Stapleton, Gem and Taylor, John, Spider diagrams. LMS Journal of Computation and Mathematics. v8. 145-194.
[12]
Lawson, Mark V., Finite Automata. 2003. CRC Press.
[13]
Alexandru Mateescu, Arto Salomaa, Formal Languages: An Introduction and a Synopsis, Handbook of Formal Languages, Word, Language, Grammar, vol. 1, Springer-Verlag, New York, USA, 1997, pp. 1-39.
[14]
Jean-Eric Pin, Syntactic Semigroups, Handbook of formal languages, Word, Language, Grammar, vol. 1, Springer-Verlag, New York, USA, 1997, pp. 679-746.
[15]
Michael O Rabin, Dana Scott, Finite automata and their decision problems, IBM Journal of Research Development (1959) 114-125.
[16]
Marcel-Paul Schützenberger, On finite monoids having only trivial subgroups, Information and Control (1965) 190-194.
[17]
Shin, S.-J., The Logical Status of Diagrams. 1994. Cambridge University Press.
[18]
Gem Stapleton, Reasoning with Constraint Diagrams, PhD Thesis, University of Brighton, August 2004.
[19]
Stapleton, Gem, Howse, John and Taylor, John, A decidable constraint diagram reasoning system. Journal of Logic and Computation. v15 iDecember (6). 975-1008.
[20]
Stapleton, Gem, Thompson, Simon, Howse, John and Taylor, John, The expressiveness of spider diagrams. Journal of Logic and Computation. v14 iDecember (6). 857-880.
[21]
Finite Automata, Formal Logic, and Circuit Complexity. 1994. Birkhäuser.
[22]
Thomas, Wolfgang, Classifying regular events in symbolic logic. Journal of Computer and System Sciences. v25. 360-376.
[23]
Urbas, Matej and Jamnik, Mateja, Heterogeneous proofs: spider diagrams meet higher-order provers. . In: van Eekelen, Marko, Geuvers, Herman, Schmaltz, Julien, Wiedijk, Freek (Eds.), Interactive Theorem Proving, Lecture Notes in Computer Science, vol. 6898. Springer-Verlag. pp. 376-382.
- On the expressiveness of spider diagrams and commutative star-free regular languages
Recommendations
On the expressiveness of second-order spider diagrams
Existing diagrammatic notations based on Euler diagrams are mostly limited in expressiveness to monadic first-order logic with an order predicate. The most expressive monadic diagrammatic notation is known as spider diagrams of order. A primary ...
Nondeterministic state complexity of star-free languages
We investigate the nondeterministic state complexity of several operations on finite automata accepting star-free and unary star-free languages. It turns out that in most cases exactly the same tight bounds as for general regular languages are reached. ...
Regular patterns, regular languages and context-free languages
In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier Ltd.
Publisher
Academic Press, Inc.
United States
Publication History
Published: 01 August 2013
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Jan 2025
Other Metrics
Citations
Cited By
View all- Chapman PStapleton GDelaney A(2018)On the expressiveness of second-order spider diagramsJournal of Visual Languages and Computing10.1016/j.jvlc.2013.07.00224:5(327-349)Online publication date: 26-Dec-2018