Article

Free access

An algebraic model for string patterns

Author:

Glenn F. StewartAuthors Info & Claims

POPL '75: Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages

Pages 167 - 184

https://doi.org/10.1145/512976.512994

Published: 01 January 1975 Publication History

PDF eReader

References

[1]

{Birkhoff 1967} G. Birkhoff, Lattice Theory, American Mathematical Society Colloguium Publications, vol. XXV, American Mathematical Society.

Google Scholar

[2]

{Cohen and Wegstein 1965} K. Cohen and J. H. Wegstein, "AXLE: An Axiomatic Language for String Transformations", CACM 8, 11.

Digital Library

Google Scholar

[3]

{di Forino 1968} A. C. di Forino, "String Processing Languages and Generalized Markov Algorithms", Symbol Manipulation Languages and Techniques, Proceedings of the IFIP Work-Conference on Symbol Manipulation Languages, D. G. Bobrow (ed.), North Holland Publishing Company.

Google Scholar

[4]

{Donahue 1974} J. Donahue, "Scottery", University of Toronto, Department of Computer Science, unpublished.

Google Scholar

[5]

{Doyle 1973} J. N. Doyle, "A New Approach to the Analysis and Synthesis of Strings", S4D38a, University of Arizona, Department of Computer Science.

Google Scholar

[6]

{Earley 1974} J. Earley, "High Level Operations in Automatic Programming", SIGPLAN Notices 9,4.

Digital Library

Google Scholar

[7]

{Farber et al. 1964} D. J. Farber, R. E. Griswold, I. P. Polonsky, "SNOBOL, A String Manipulation Language", JACM 11.

Digital Library

Google Scholar

[8]

{Galler and Perlis 1970} B. A. Galler and J. A. Perlis, A View of Programming Lanuages, Addison-Wesley.

Digital Library

Google Scholar

[9]

{Gimpel 1973} J. F. Gimpel, "A Theory of Discrete Patterns and Their Implementation in SNOBOL4", CACM 16,2

Digital Library

Google Scholar

[10]

{Goyer 1973} P. Goyer, "La Lange SNOBOL4 et la Conformité Chaine-modele", Ph.D. Thesis, Université de Montréal.

Google Scholar

[11]

{Griswold et al. 1971} R. E. Griswold, J. F. Poage, I. P. Polonsky, The SNOBOL4 Programming Language, second edition, Prentice-Hall.

Digital Library

Google Scholar

[12]

{Griswold 1973} R. E. Griswold, "New Control Mechanism and Syntax for SNOBOL4", S4D35a, University of Arizona, Department of Computer Science.

Google Scholar

[13]

{Jacobson 1951} N. Jacobson, Lectures in Abstract Algebra, D. Van Nostrand.

Google Scholar

[14]

{Minsky 1967} M. L. Minsky, Computation; Finite and Infinite Machines, Prentice-Hall.

Digital Library

Google Scholar

[15]

{Reboh and Sacerdoti 1973} R. Reboh and E. Sacerdoti, "A Preliminary QLISP Manual", Stanford Research Institute, Artificial Intelligence Centre, Technical Note 81.

Google Scholar

[16]

{Redei 1967} L Redei, Algebra, Pergammon Press.

Google Scholar

[17]

{Scott 1970} D. Scott, "Outline of a Mathematical Theory of Computation", Proceedings of the Fourth Annual Princeton Conference on Information Science and Systems, Princeton.

Google Scholar

[18]

{Scott 1972} D. Scott, "Lattice Theory, Data Types and Formal Semantics", NYU Symposium on Formal Semantics, Prentice-Hall.

Google Scholar

[19]

{Stewart 1974} G. F. Stewart, "An Algebraic Model for String Patterns", University of Toronto, Computer Systems Research Group Technical Report No. CSRG-39.

Google Scholar

[20]

{Tennent 1973} R. D. Tennent, "Mathematical Semantics and Design of Programming Languages", University of Toronto, Department of Computer Science Technical Report No. 59.

Google Scholar

[21]

{Yngve 1972} V. H. Yngve, Computer Programming With COMIT IT, M.I.T. Press.

Google Scholar

Cited By

View all

Zhang JWang YTay Y(2018)A collaborative framework for tweaking properties in a synthetic datasetProceedings of the VLDB Endowment10.14778/3229863.323624711:12(2010-2013)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.14778/3229863.3236247
Aebeloe CMontoya GSetty VHose K(2018)Discovering diversified paths in knowledge basesProceedings of the VLDB Endowment10.14778/3229863.323624511:12(2002-2005)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.14778/3229863.3236245
Li G(2017)Human-in-the-loop data integrationProceedings of the VLDB Endowment10.14778/3137765.313783310:12(2006-2017)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.14778/3137765.3137833
Show More Cited By

Recommendations

String Indexing for Patterns with Wildcards

We consider the problem of indexing a string t of length n to report the occurrences of a query pattern p containing m characters and j wildcards. Let occ be the number of occurrences of p in t, and σ the size of the alphabet. We obtain the following ...
Shortest string containing all permutations

In this paper, we consider the problem of constructing a shortest string of {1,2,...,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less ...
The patterns of permutations
Kleitman and combinatorics: a celebration

Let n,k be positive integers, with k ≤ n, and let τ be a fixed permutation of {1,...,k}. We will call τ the pattern. We will look for the pattern τ in permutations σ of n letters. A pattern τ is said to occur in a permutation σ if there are integers 1 ≤ ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

POPL '75: Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages

January 1975

242 pages

ISBN:9781450373517

DOI:10.1145/512976

Conference Chairs:
Robert M. Graham
City College of New York, New York, NY
,
Michael A. Harrison
University of California, Berkeley, CA
,
Program Chair:
John C. Reynolds
Syracuse University, Syracuse, NY

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1975

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

POPL '75 Paper Acceptance Rate 23 of 100 submissions, 23%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
299
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)5

Reflects downloads up to 26 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang JWang YTay Y(2018)A collaborative framework for tweaking properties in a synthetic datasetProceedings of the VLDB Endowment10.14778/3229863.323624711:12(2010-2013)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.14778/3229863.3236247
Aebeloe CMontoya GSetty VHose K(2018)Discovering diversified paths in knowledge basesProceedings of the VLDB Endowment10.14778/3229863.323624511:12(2002-2005)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.14778/3229863.3236245
Li G(2017)Human-in-the-loop data integrationProceedings of the VLDB Endowment10.14778/3137765.313783310:12(2006-2017)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.14778/3137765.3137833
Alawini ADavidson SHu WWu Y(2017)Automating data citation in CiteDBProceedings of the VLDB Endowment10.14778/3137765.313779910:12(1881-1884)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.14778/3137765.3137799
Pang ZWu SChen GChen KShou L(2017)FlashViewProceedings of the VLDB Endowment10.14778/3137765.313779610:12(1869-1872)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.14778/3137765.3137796
Huang KBhowmick SZhou SChoi B(2017)PICASSOProceedings of the VLDB Endowment10.14778/3137765.313779410:12(1861-1864)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.14778/3137765.3137794
Niu XArab BLee SFeng SZou XGawlick DKrishnaswamy VLiu ZGlavic B(2017)Debugging transactions and tracking their provenance with reenactmentProceedings of the VLDB Endowment10.14778/3137765.313779310:12(1857-1860)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.14778/3137765.3137793
Ré CSuciu D(2008)Approximate lineage for probabilistic databasesProceedings of the VLDB Endowment10.14778/1453856.14539431:1(797-808)Online publication date: 1-Aug-2008
https://dl.acm.org/doi/10.14778/1453856.1453943
Klint P(2005)Design considerations for string processing languagesA Study in String Processing Languages10.1007/3-540-16041-8_2(17-37)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-16041-8_2
Emanuelson P(2005)From abstract model to efficient compilation of patternsInternational Symposium on Programming10.1007/3-540-11494-7_8(91-104)Online publication date: 27-May-2005
https://doi.org/10.1007/3-540-11494-7_8
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

String Indexing for Patterns with Wildcards

Shortest string containing all permutations

The patterns of permutations