Article

On nominal regular languages with binders

Authors:

Alexander Kurz,

Tomoyuki Suzuki,

Emilio TuostoAuthors Info & Claims

FOSSACS'12: Proceedings of the 15th international conference on Foundations of Software Science and Computational Structures

Pages 255 - 269

https://doi.org/10.1007/978-3-642-28729-9_17

Published: 24 March 2012 Publication History

Abstract

We investigate regular languages on infinite alphabets where words may contain binders on names. To this end, classical regular expressions and automata are extended with binders. We prove the equivalence between finite automata on binders and regular expressions with binders and investigate closure properties and complementation of regular languages with binders.

References

[1]

Aboul-Hosn, K., Kozen, D.: Local variable scoping and kleene algebra with tests. J. Log. Algebr. Program. 76(1), 3-17 (2008)

[2]

Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56(3) (2009)

Digital Library

[3]

Arbib, M. A., Manes, E. G.: Machines in a category: An expository introduction. SIAM Review 16(163-192), 285-302 (1974)

[4]

Bojanczyk, M.: Data monoids. In: STACS, pp. 105-116 (2011)

[5]

Bojanczyk, M., Klin, B., Lasota, S.: Automata with group actions. In: IEEE Symposium on Logic in Computer Science, pp. 355-364 (2011)

Digital Library

[6]

Ciancia, V.: Nominal Sets, Accessible Functors and Final Coalgebras for Named Sets. PhD thesis, Dipartimento di Informatica, Universit`a di Pisa (2008) forthcoming

[7]

Ciancia, V., Montanari, U.: Symmetries, local names and dynamic (de)-allocation of names. Inf. Comput. 208(12), 1349-1367 (2010)

Digital Library

[8]

Ciancia, V., Tuosto, E.: A novel class of automata for languages on infinite alphabets. Technical Report CS-09-003, Leicester (2009)

[9]

Engelfriet, J., Hoogeboom, H. J.: Tree-walking pebble automata. In: Jewels are Forever, pp. 72-83 (1999)

[10]

Fernández, M., Gabbay, M.: Nominal rewriting. Inf. Comput. 205(6), 917-965 (2007)

Digital Library

[11]

Fiore, M. P., Staton, S.: Comparing operational models of name-passing process calculi. Inf. Comput. 204(4), 524-560 (2006)

Digital Library

[12]

Gabbay, M., Ciancia, V.: Freshness and Name-Restriction in Sets of Traces with Names. In: Hofmann, M. (ed.) FOSSACS 2011. LNCS, vol. 6604, pp. 365-380. Springer, Heidelberg (2011)

Digital Library

[13]

Gabbay, M., Pitts, A.: A new approach to abstract syntax involving binders. In: Symbolic on Logics in Comput Science, pp. 214-224 (1999)

Digital Library

[14]

Gadducci, F., Miculan, M., Montanari, U.: About permutation algebras (pre)sheaves and named sets. Higher-Order and Symbolic Computation 19(2-3), 283-304 (2006)

Digital Library

[15]

Hopcroft, J. E., Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison Wesley (2000)

Digital Library

[16]

Kaminski, M., Francez, N.: Finite-memory automata. TCS 134(2), 329-363 (1994)

Digital Library

[17]

Kurz, A., Suzuki, T., Tuosto, E.: Towards nominal formal languages. CoRR, abs/1102.3174 (2011)

[18]

Montanari, U., Pistore, M.: p-Calculus, Structured Coalgebras, and Minimal HD-Automata. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 569-578. Springer, Heidelberg (2000)

Digital Library

[19]

Pistore, M.: History Dependent Automata. PhD thesis, Dip. di Informatica - Pisa (1999)

[20]

Pitts, A., Stark, I.: Observable Properties of Higher Order Functions that Dynamically Create Local Names, orWhat's New? In: Borzyszkowski, A. M., Sokolowski, S. (eds.) MFCS 1993. LNCS, vol. 711, pp. 122-141. Springer, Heidelberg (1993)

Digital Library

[21]

Pouillard, N., Pottier, F.: A fresh look at programming with names and binders. In: Proceeding of the 15th ACM SIGPLAN International Conference on Functional Programming, pp. 217-228 (2010)

Digital Library

[22]

Segoufin, L.: Automata and Logics for Words and Trees over an Infinite Alphabet. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 41-57. Springer, Heidelberg (2006)

Digital Library

[23]

Shinwell, M., Pitts, A., Gabbay, M.: Freshml: programming with binders made simple. In: Proceedings of the Eighth ACM SIGPLANInternational Conference on Functional Programming, pp. 263-274 (2003)

Digital Library

[24]

Stirling, C.: Dependency Tree Automata. In: de Alfaro, L. (ed.) FOSSACS 2009. LNCS, vol. 5504, pp. 92-106. Springer, Heidelberg (2009)

Digital Library

[25]

Stone, M. H.: Postulates for boolean algebras and generalized boolean algebras. American Journal of Mathematics 57(4), 703-732 (1935)

[26]

Tzevelekos, N.: Fresh-Register Automata. In: Symposium on Principles of Programming Languages, pp. 295-306. ACM (2011)

Digital Library

[27]

Weikum, G., Vossen, G.: Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery. Morgan Kaufmann (2002)

Digital Library

Cited By

Hofman PJuzepczuk MLasota SPattathurajan MGorla D(2021)Parikh's theorem for infinite alphabetsProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470626(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470626
Cledou GProença JSputh BVerhulst E(2019)Coordination of Tasks on a Real-Time OSCoordination Models and Languages10.1007/978-3-030-22397-7_15(250-266)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-22397-7_15
Schröder LKozen DMilius SWiβmann T(2017)Nominal Automata with Name BindingProceedings of the 20th International Conference on Foundations of Software Science and Computation Structures - Volume 1020310.1007/978-3-662-54458-7_8(124-142)Online publication date: 22-Apr-2017
https://dl.acm.org/doi/10.1007/978-3-662-54458-7_8
Show More Cited By

Index Terms

On nominal regular languages with binders
1. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages

Index terms have been assigned to the content through auto-classification.

Recommendations

Unambiguity in timed regular languages: automata and logics
FORMATS'10: Proceedings of the 8th international conference on Formal modeling and analysis of timed systems

Unambiguous languages (UL), originally defined by Schutzenberger using unambiguous polynomials, are a robust subclass of regular languages. They have many diverse characterizations: they are recognized by partially-ordered two-way deterministic automata ...
Restarting Transducers, Regular Languages, and Rational Relations

A (nonforgetting) restarting transducer is a (nonforgetting) restarting automaton that is equipped with an output function. Accordingly, restarting transducers compute binary relations, and deterministic restarting transducers compute functions. Here we ...
Regular Expressions for Languages over Infinite Alphabets

In this paper we introduce a notion of a regular expression over infinite alphabets and show that a language is definable by an infinite alphabet regular expression if and only if it is accepted by finite-state unification based automaton - a model of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

FOSSACS'12: Proceedings of the 15th international conference on Foundations of Software Science and Computational Structures

March 2012

481 pages

ISBN:9783642287282

Editor:
Lars Birkedal
IT University of Copenhagen, Rued Langgaards Vej 7, Copenhagen, Denmark

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 24 March 2012

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hofman PJuzepczuk MLasota SPattathurajan MGorla D(2021)Parikh's theorem for infinite alphabetsProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470626(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470626
Cledou GProença JSputh BVerhulst E(2019)Coordination of Tasks on a Real-Time OSCoordination Models and Languages10.1007/978-3-030-22397-7_15(250-266)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-22397-7_15
Schröder LKozen DMilius SWiβmann T(2017)Nominal Automata with Name BindingProceedings of the 20th International Conference on Foundations of Software Science and Computation Structures - Volume 1020310.1007/978-3-662-54458-7_8(124-142)Online publication date: 22-Apr-2017
https://dl.acm.org/doi/10.1007/978-3-662-54458-7_8
Kozen DMamouras KPetrişan DSilva A(2015)Nominal Kleene CoalgebraProceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming - Volume 913510.1007/978-3-662-47666-6_23(286-298)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-662-47666-6_23
Degano PFerrari GMezzetti G(2013)Towards nominal context-free model-checkingProceedings of the 18th international conference on Implementation and Application of Automata10.1007/978-3-642-39274-0_11(109-121)Online publication date: 16-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39274-0_11
Kurz ASuzuki TTuosto E(2012)A characterisation of languages on infinite alphabets with nominal regular expressionsProceedings of the 7th IFIP TC 1/WG 202 international conference on Theoretical Computer Science10.1007/978-3-642-33475-7_14(193-208)Online publication date: 26-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33475-7_14

View Options

View options

Media

Figures

Other

Tables

View Table of Contents