5th International PhD School in Formal Languages and Applications

2006

1st TERM

Programmes

LANGUAGES

Alexander Okhotin, Rovira i Virgili University, Tarragona

  1. Formal languages. Basic operations on languages. Automata and grammars. Syntax and parsing
  2. Representation of languages. Descriptional complexity. Language families. Operations on languages and their properties. Closure under operations
  3. Computability. Basic models of computation. Complexity of computation. Decision problems for formal languages
  4. Languages of different objects (infinite words, finite and infinite trees). Different kinds of representation

References

Harrison, M.A. (1978), Introduction to Formal Language Theory. Addison-Wesley, Reading, MA.

Hopcroft, J.E. & J.D. Ullman (1979), Introduction to Automata Theory, Languages, and Computation, 1st ed. Addison-Wesley, Reading, MA.

Rozenberg, G. & A. Salomaa, eds. (1997), Handbook of Formal Languages, 3 vols. Springer, Berlin.

Salomaa, A. (1973), Formal Languages. Academic Press, New York.

Sipser, M. (1997), Introduction to the Theory of Computation, 2nd ed. 2005. PWS Publishing Company, Boston, MA.

COMBINATORICS ON WORDS

Tero Harju, University of Turku

  1. Defect theorem
  2. Critical factorization theorem
  3. Ehrenfeucht’s conjecture

References

Lothaire, M. (1983), Combinatorics on Words. Addison-Wesley, Reading, MA.

Lothaire, M. (2002), Algebraic Combinatorics of Words. Cambridge University Press, Cambridge.

REGULAR GRAMMARS

Masami Ito, Kyoto Sangyo University

  1. Regular grammars and languages
  2. Syntactic congruences
  3. Deterministic and nondeterministic automata
  4. Operations on languages
  5. Shuffle products and closures
  6. Directable automata and languages

References

Hopcroft, J.E. & J.D. Ullman (1979), Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA.

Ito, M. (2004), Algebraic Theory of Automata and Languages. World Scientific, Singapore.

Salomaa, A. (1981), Jewels of Formal Language Theory. Computer Science Press, Rockville, MD.

CONTEXT-FREE GRAMMARS

Manfred Kudlek, University of Hamburg

  1. Normal forms
  2. Iteration lemmata
  3. Derivation trees, ambiguity
  4. Relation to pushdown automata
  5. Deterministic context-free languages
  6. Complexity of analysis
  7. Decidability problems
  8. Closure properties
  9. Algebraic characterization

References

Harrison, M.A. (1978), Introduction to Formal Language Theory. Addison-Wesley, Reading, MA.

Hopcroft, J.E. & J.D. Ullman (1979), Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA.

Salomaa, A. (1973), Formal Languages. Academic Press, New York.

MILDLY CONTEXT-SENSITIVE GRAMMARS

Henning Bordihn, University of Potsdam

  1. Motivation, definitions and background
  2. Tree-adjoining grammars and equivalent devices
  3. Further approaches to mild context-sensitivity

References

Joshi, A.K. (1985), How much context-sensitivity is required to provide reasonable structural descriptions: tree adjoining grammars, in D. Dowty, L. Karttunen & A. Zwicky, eds., Natural Language Parsing: Psychological, Computational, and Theoretical Perspectives: 206-250. Cambridge University Press, Cambridge.

Joshi, A.K. & Y. Schabes (1997), Tree adjoining grammars, in G. Rozenberg & A. Salomaa, eds., Handbook of Formal Languages, vol. 3: 69-124. Springer, Berlin.

Kudlek, M., C. Martín-Vide, A. Mateescu & V. Mitrana (2003), Contexts and the concept of mild context-sensitivity, Linguistics and Philosophy, 26: 703-725.

Marcus, S. (1969), Contextual grammars and natural languages, in G. Rozenberg & A. Salomaa, eds., Handbook of Formal Languages, vol. 2: 215-235. Springer, Berlin.

Partee, B.H., A.G.B. ter Meulen & R.E. Wall (1990), Mathematical Methods in Linguistics. Kluwer, Dordrecht.

Pullum, G.K. & G. Gazdar (1982), Natural languages and context-free languages, Linguistics and Philosophy, 4: 471-504.

Roach, K. (1987), Formal properties of head grammars, in A. Manaster Ramer, ed., Mathematics of Language: 293-347. John Benjamins, Amsterdam.

Shieber, S.M. (1985), Evidence against the context-freeness of natural language, Linguistics and Philosophy, 8: 333-343.

Steedman, M. (1985), Dependency and coordination in the grammar of Dutch and English, Language, 61: 523-568.

Vijay-Shanker, K. & D.J. Weir (1994), The equivalence of four extensions of context-free grammars, Mathematical Systems Theory, 87: 511-546.

INFINITE WORDS

Juhani Karhumäki, University of Turku

  1. Mechanisms to generate infinite words
  2. Repetitions in infinite words and applications
  3. Subword complexity of infinite words

References

Choffrut, C. & J. Karhumäki (1997), Combinatorics of words, in G. Rozenberg & A. Salomaa, eds., Handbook of Formal Languages, vol. I: 329-438. Springer, Berlin.

Fogg, P. (2002), Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Mathematics 1794. Springer, Berlin.

Lothaire, M. (1983), Combinatorics on Words. Addison-Wesley, Reading, MA.

Lothaire, M. (2002), Algebraic Combinatorics of Words. Cambridge University Press, Cambridge.

FINITE AUTOMATA

Sheng Yu, University of Western Ontario, London ON, Canada

  1. Deterministic and nondeterministic finite automata
  2. Regular expressions
  3. Automata minimization
  4. State complexities of regular languages
  5. Alternating finite automata
  6. Equational representation of regular languages
  7. Finite transducers and rational relations
  8. Finite languages and cover automata
  9. Fuzzy automata and fuzzy regular expressions

References

Berstel, J. (1979), Transductions and Context-free Languages. Teubner, Stuttgart.

Campeanu, C., N. Sântean & S. Yu (2001), Minimal cover-automata for finite languages, Theoretical Computer Science, 267: 3-16.

Fellah, A., H. Jürgensen & S. Yu (1990), Constructions on alternating finite automata, International Journal of Computer Mathematics, 35(3-4): 117-132.

Hopcroft, J.E. & J.D. Ullman (1979), Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA.

Lewis, H.R. & C.H. Papadimitriou (1998), Elements of the Theory of Computation, 2nd ed. Prentice-Hall, Englewood Cliffs, NJ.

Mateescu, A., A. Salomaa, K. Salomaa & S. Yu (1995), Lexical analysis with a simple finite-fuzzy-automaton model, Journal of Universal Computer Science, 1(5): 292-311.

Salomaa, A. (1969), Theory of Automata. Pergamon, Oxford.

Salomaa, A. (1985), Computation and Automata. Cambridge University Press, Cambridge.

Szilard, A., S. Yu, K. Zhang & J. Shallit (1992), Characterizing regular languages with polynomial densities, in I.M. Havel & V. Koubek, eds., Mathematical Foundations of Computer Science 1992, Lecture Notes in Computer Science 629: 494-503. Springer, Berlin.

Wood, D. (1987), Theory of Computation. John Wiley, New York.

Yu, S. (1997), Regular languages, in G. Rozenberg & A. Salomaa, eds., Handbook of Formal Languages, vol. I: 41-110. Springer, Berlin.

Yu, S. (1999), State complexity of regular languages, Journal of Automata, Languages and Combinatorics, 6(2): 221-233.

CONTEXT-SENSITIVE GRAMMARS

Victor Mitrana, Rovira i Virgili University, Tarragona

  1. When and why context-freeness is not sufficient
  2. Normal forms for context-sensitive grammars
  3. Workspace theorem
  4. Linear bounded automata. The LBA problem
  5. Closure properties
  6. Decidable properties
  7. Context-sensitive grammars generating context-free languages

References

Hopcroft, J.E. & J.D. Ullman (1979), Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA.

Immerman, N. (1988), Nondeterministic space is closed under complementation, SIAM Journal of Computing, 17(5): 935-938.

Kuroda, S.Y. (1964), Classes of languages and linear bounded automata, Information and Control, 7: 207-223.

Rozenberg, G. & A. Salomaa, eds. (1997), Handbook of Formal Languages, 3 vols. Springer, Berlin.

Salomaa, A. (1973), Formal Languages. Academic Press, New York.

Szelepcseny, R. (1988), The method of forced enumeration for nondeterministic automata, Acta Informatica, 26: 279-284.

PUSHDOWN AUTOMATA

Hendrik Jan Hoogeboom, Leiden University

  1. Acceptance by final state and by empty stack: equivalence
  2. Equivalence of pushdown automata and context-free grammars
  3. Determinism, real-time property
  4. LL(1) parsing

References

Autebert, J.-M., J. Berstel & L. Boasson (1997), Context-free languages and pushdown automata, in G. Rozenberg & A. Salomaa, eds., Handbook of Formal Languages, vol. I. Springer, Berlin.

Hopcroft, J.E., R. Motwani & J.D. Ullman (2001), Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA.

PARTIAL WORDS

Francine Blanchet-Sadri, University of North Carolina Greensboro

Strings of symbols from a finite alphabet, also referred to as words, have long been studied. This course will investigate partial words, that are strings that may contain a number of “do not know” symbols. While a word can be described by a total function, a partial word can be described by a partial function. More precisely, a partial word of length n over a finite alphabet Ais a partial function from {0,...,n-1}into A. Elements of {0,...,n-1} without an image are called holes (a word is just a partial word without holes). In this course, we will first examine to which extent some properties of words, such as commutativity and conjugacy, remain true for partial words. We will then extend to partial words some fundamental periodicity results on words: (1) the well known and basic result of Fine and Wilf which intuitively determines how far two periodic events have to match in order to guarantee a common period; (2) the well known critical factorization theorem which intuitively states that the minimal period of a word is always locally detectable in at least one position of the word; and (3) the well known and unexpected result of Guibas and Odlyzko which states that the set of all periods of a word is independent of the alphabet size. We will finally study two fundamental properties of partial words: primitivity and borderedness. Lecture Notes “F. Blanchet-Sadri, Partial Words, ©2006 by Francine Blanchet-Sadri” will be distributed. Topics (and related links) include:

  1. Basics
  1. Preliminaries on partial words

1.1.1.Background

1.1.2.Periods and weak periods

1.1.3.Compatibility (x  y)

1.2.Combinatorial properties of partial words

1.2.1.Equidivisibility: ux  vy

1.2.2.Commutativity: xy  yx

1.2.3.Conjugacy: xz  zy

  1. Periodicity
  2. Fine and Wilf's theorem

2.1.1.The case of zero or one hole

2.1.2.The case of two or three holes

2.1.3.Special partial words

2.1.4.Graphs associated with partial words

2.1.5.The main result

2.2.Critical factorization theorem

2.2.1.Orderings

2.2.2.The zero­hole case

2.2.3.The main result: first version

2.2.4.The main result: second version

2.2.5.Tests

2.3.Guibas and Odlyzko's theorem

2.3.1.The zero­hole case

2.3.2.The main result

2.3.3.The algorithm

  1. Primitivity
  2. Primitive partial words and fundamental properties

3.1.1.Testing primitivity on partial words

3.1.2.Powers of primitive partial words

3.1.3.Existence of primitive partial words

3.2.Unbordered partial words

3.2.1.Concatenations of prefixes

3.2.2.Critical factorizations

3.2.3.Conjugates

The following link contains useful information on relevant papers and recommended literature related to the course. They include:

References

Berstel, J. & L. Boasson (1999), Partial words and a theorem of Fine and Wilf, Theoretical Computer Science, 218: 135-141.

Blanchet­Sadri, F. (2004), Periodicity on partial words, Computers and Mathematics with Applications, 47: 71-82.

Blanchet­Sadri, F. (2004), Codes, orderings and partial words, Theoretical Computer Science, 329: 177-202.

Blanchet­Sadri, F. (2005), Primitive partial words, Discrete Applied Mathematics, 148: 195-213.

Blanchet­Sadri, F. & A.R. Anavekar, Testing primitivity on partial words,

Blanchet­Sadri, F., D.D. Blair & R.V. Lewis, Equations on partial words,

Blanchet­Sadri, F. & A. Chriscoe (2004), Local periods and binary partial

words: an algorithm, Theoretical Computer Science, 314: 189-216. (

Blanchet­Sadri, F., K. Corcoran & J. Nyberg, Fine and Wilf's periodicity result on partial words and consequences,

Blanchet­Sadri, F. & S. Duncan (2005), Partial words and the critical factorization theorem, Journal of Combinatorial Theory, Series A, 109: 221-245. (

Blanchet­Sadri, F. & R.A. Hegstrom (2002), Partial words and a theorem of Fine and Wilf revisited, Theoretical Computer Science, 270: 401-419.

Blanchet­Sadri, F. & D.K. Luhmann (2002), Conjugacy on partial words, Theoretical Computer Science, 289: 297-312.

Blanchet­Sadri, F. & N.D. Wetzler, Partial words and the critical factorization theorem revisited,

Césari, Y. & M. Vincent (1978), Une caractérisation des mots périodiques, Comptes Rendues de l’Académie des Sciences de Paris, 268: 1175-1177.

Choffrut, C. & J. Karhumäki (1997), Combinatorics of words, in G. Rozen­

berg & A. Salomaa, eds., Handbook of Formal Languages, vol. 1, ch. 6: 329-438. Springer, Berlin.

Crochemore, M. & D. Perrin (1991), Two­way string matching, Journal of the ACM, 38: 651-675.

Duval, J.P. (1982), Relationship between the period of a finite word and the

length of its unbordered segments, Discrete Mathematics, 40: 31-44.

Fine, N.J. & H.S. Wilf (1965), Uniqueness theorems for periodic functions,

Proceedings of the American Mathematical Society, 16: 109-114.

Guibas, L.J. & A.M. Odlyzko (1981), Periods in strings, Journal of Combinatorial Theory, Series A, 30: 19-42.

Halava, V., T. Harju & L. Ilie (2000), Periods and binary words, Journal of

Combinatorial Theory, Series A, 89: 298-303.

Lothaire, M. (1983), Combinatorics on Words. Addison­Wesley, Reading, MA. (Cambridge University Press, Cambridge, 1997)

Lothaire, M. (2002), Algebraic Combinatorics of Words. Cambridge University Press, Cambridge.

Lothaire, M. (2005), Applied Combinatorics on Words. Cambridge University Press, Cambridge.

Shur, A.M. & Y.V. Gamzova (2004), Partial words and the periods' interaction property, Izvestiya RAN, 68: 199-222.

Shur, A.M. & Y.V. Konovalova (2001), On the periods of partial words, in J. Sgall, A. Pultr & P. Kolman, eds., Mathematical Foundations of Computer Science 2001, Lecture Notes in Computer Science 2136: 657-665. Springer, Berlin.

Shyr, H.J. (1991), Free Monoids and Languages. Hon Min Book Company,

Taichung.

TURING MACHINES

Holger Petersen, University of Stuttgart

References

Ben-Amram, A.M., O. Berkman & H. Petersen (2003), Element distinctness on one-tape Turing machines, Acta Informatica, 40: 81-94.

Cocke, J. & M.L. Minsky (1964), Universality of tag systems with P=2, Journal of the ACM, 11(1): 15-20.

Green, M.W. (1964), A lower bound on Rado's Sigma Function for binary Turing machines, in Switching Circuit Theory and Logical Design, Proceedings of the Fifth Annual Symposium: 91-94, The Institute of Electrical and Electronics Engineers.

Hopcroft, J.E. & J.D. Ullman (1979), Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA.

Kushilevitz, E. & N. Nisan (1997), Communication Complexity. Cambridge University Press, Cambridge.

Minsky, M.L. (1961), Recursive unsolvability of Post's problem of “tag” and other topics in the theory of Turing machines, Annals of Mathematics, 74: 437-455.

Minsky, M.L. (1967), Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, NJ.

Post, E.L. (1943), Formal reductions of the classical combinatorial decision problem, American Journal of Mathematics, 65: 197-215.

Rado, T. (1962), On non-computable functions, The Bell System Technical Journal, 41: 877-884.

Wang, H. (1957), A variant to Turing's theory of computing machines, Journal of the ACM, 4: 63-92.

Wang, H. (1963), Tag systems and lag systems, Math. Ann., 152: 65-74.

Wagner, K. & G. Wechsung (1986), Computational Complexity. Reidel, Dordrecht.

VARIETIES OF FORMAL LANGUAGES

Jean-Éric Pin, CNRS and University Paris 7

  1. Rational and recognizable sets
  2. Finite automata and recognizable sets
  3. Automata and semigroups
  4. A bit of history...
  5. Star-free languages
  6. Piecewise testable languages
  7. Locally testable languages
  8. Varieties, Eilenberg's theorem
  9. Elementary semigroup theory
  10. More examples of varieties
  11. Overview of recent advances

References

To be distributed.

DESCRIPTIONAL COMPLEXITY OF AUTOMATA AND GRAMMARS

Detlef Wotschke, University of Frankfurt

  1. Major results in descriptional complexity of automata and grammars
  2. Relationship between the use of limited resources (like nondeterminism, ambiguity, lookahead, etc.) and their effect on the smallest possible descriptions or representations of objects such as finite automata, probabilistic automata, pushdown automata, context-free grammars, etc.

References

Bucher, W., H.A. Maurer, K. Culik, II & D. Wotschke (1981), Concise description of finite languages, Theoretical Computer Science, 14(3): 227-246.

Geller, M.M., H.B. Hunt, III, T.G. Szymanski & J.D. Ullman (1977), Economy of description of parsers, DPDA's, and PDA's, Theoretical Computer Science, 4(2): 143-153.

Goldstine, J., C.M.R. Kintala & D. Wotschke (1990), On measuring nondeterminism in regular languages, Information and Computation, 86(2): 179-194.

Goldstine, J., H. Leung & D. Wotschke (1992), On the relation between ambiguity and nondeterminism in finite automata, Information and Computation, 100(2): 261-270.

Goldstine, J., H. Leung & D. Wotschke (1997), Measuring nondeterminism in pushdown automata, in R. Reischuk & M. Morvan, eds., Theoretical Aspects of Computer Science 1997, Lecture Notes in Computer Science 1200: 295-306. Springer, Berlin.

Goldstine, J., J.K. Price & D. Wotschke (1982), A pushdown automaton or a context-free grammar: which is more economical?, Theoretical Computer Science, 18(1): 33-40.

Goldstine, J., J.K. Price & D. Wotschke (1982), On reducing the number of states in a PDA, Mathematical Systems Theory, 15(4): 315-321.

Goldstine, J., J.K. Price & D. Wotschke (1993), On reducing the number of stack symbols in a PDA, Mathematical Systems Theory, 26(4): 313-326.

Hartmanis, J. (1980), On the succinctness of different representations of languages, SIAM Journal on Computing, 9(1): 114-120.

Herzog, C. (1997), Pushdown automata with bounded nondeterminism and bounded ambiguity, Theoretical Computer Science, 181(1): 141-157.

Kappes, M. (2000), Descriptional complexity of deterministic finite automata with multiple initial states, Journal of Automata, Languages and Combinatorics, 5(3): 269-278.

Kintala, C.M.R. (1978), Refining nondeterminism in context-free languages, Mathematical Systems Theory, 12(1): 1-8.

Kintala, C.M.R., K.-Y. Pun & D. Wotschke (1993), Concise representations of regular languages by degree and probabilistic finite automata, Mathematical Systems Theory, 26(4): 379-395.

Kintala, C.M.R. & D. Wotschke (1980), Amounts of nondeterminism in finite automata, Acta Informatica, 13(2): 199-204.

Kintala, C.M.R. & D. Wotschke (1986), Concurrent conciseness of degree, probabilistic, nondeterministic and deterministic finite automata, in B. Monien & G. Vidal-Naquet, eds., Theoretical Aspects of Computer Science 1986, Lecture Notes in Computer Science 210: 291-305. Springer, Berlin.

Leung, H. (1998), On finite automata with limited nondeterminism, Acta Informatica, 35(7): 595-624.

Leung, H. (2000), On a family of nondeterministic finite automata, Journal of Automata, Languages and Combinatorics, 5(3): 235-244.

Leung, H. & D. Wotschke (2000), On the size of parsers and LR(k)-grammars, Theoretical Computer Science, 242(1-2): 59-69.

Malcher, A. (2001), Descriptional complexity of cellular automata and decidability questions, in J. Dassow & D. Wotschke, eds., Proceedings of the Third International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS 2001): 123-132. Otto-von-Guericke-Universität Magdeburg, Magdeburg.

Meyer, A.R. & M.J. Fischer (1971), Economy of description by automata, grammars, and formal systems, Proceedings of the IEEE Twelfth Annual Symposium on Switching and Automata Theory. IEEE: 188-191.

Salomaa, K. & S. Yu (1991), Degrees of nondeterminism for pushdown automata, in L. Budach, ed., Fundamentals of Computation Theory 1991, Lecture Notes in Computer Science 529: 380-389. Springer, Berlin.

Salomaa, K. & S. Yu (1994), Measures of nondeterminism for pushdown automata, Journal of Computer and System Sciences, 49(2): 362-374.

Valiant, L.G. (1976), A note on the succinctness of descriptions of deterministic languages, Information and Control, 32(2): 139-145.

COMPUTATIONAL COMPLEXITY

Markus Holzer, Technical University of Munich

  1. Basics in complexity theory: sequential classes, parallel classes
  2. Fixed and general membership problems: Chomsky languages, regular languages revisited, Lindenmayer languages, other formal language classes
  3. Some other problems: finiteness etc., counting problems
  4. Operations on complexity classes
  5. Auxiliary space bounded automata with abstract storage: pushdown automata, variants of stack automata

References

Barrington, D.A. (1989), Bounded-width polynomial-size branching programs recognize exactly those languages in {{m NC}^1}, Journal of Computer and System Sciences, 38(1): 150-164.

Damm, C., M. Holzer & K.-J. Lange (1992), The parallel complexity of iterated morphisms and the arithmetic of small numbers, in I.M. Havel & V. Koubek, eds., Mathematical Foundations of Computer Science 1992, Lecture Notes in Computer Science 629: 227-235. Springer, Berlin.

Holzer, M. (1996), On emptiness and counting for alternating finite automata, in J. Dassow, G. Rozenberg & A. Salomaa, eds., Developments in Language Theory II: At the Crossroads of Mathematics, Computer Science and Biology: 88-97. World Scientific, Singapore.

Holzer, M. & K.-J. Lange (1993), On the complexities of linear LL(1) and LR(1) grammars, in Z. Ésik, ed., Fundamentals of Computation Theory 1993, Lecture Notes in Computer Science 710: 299-308. Springer, Berlin.

Holzer, M. & K.-J. Lange (1997), On the complexity of iterated insertions, in G. Păun & A. Salomaa, eds., New Trends in Formal Languages: Control, Cooperation, and Combinatorics, Lecture Notes in Computer Science 1218: 440-453. Springer, Berlin.

Lange, K.-J. (1996), Complexity and structure in formal language theory, Fundamenta Informaticae, 25(3-4): 327-352.

Monien, B. (1981), On the LBA problem, in F. Gécseg, ed., Fundamentals of Computation Theory 1981, Lecture Notes in Computer Science 117: 265-280. Springer, Berlin.

Monien, B. & I. Sudborough (1980), The interface between language theory and complexity theory, in R.V. Book, ed., Formal Languages: Perspectives and Open Problems: 287-324. Academic Press, New York.

Papadimitriou, C.H. (1994), Computational Complexity. Addison-Wesley, Reading, MA.

Sudborough, I.H. (1975), A note on tape-bounded complexity classes and linear context-free languages, Journal of the Association for Computing Machinery, 22(4): 499-500.

Sudborough, I.H. (1976), The complexity of the membership problem for some extensions of context-free languages, Computing Reviews, 19(5): 191-215.

PATTERNS

Kai Salomaa, Queen’s University, Kingston ON, Canada

  1. Pattern languages, E-patterns, NE-patterns
  2. Equivalence and inclusion problems, connection to rewriting systems
  3. Extended regex: expressions based on patterns
  4. Ambiguity in patterns and extended regex
  5. Pattern systems

References

Angluin, D. (1980), Finding patterns common to a set of strings, Journal of Computer and System Sciences, 21: 46-62.

Campeanu, C., K. Salomaa & S. Yu (2003), A formal study of practical regular expressions, International Journal of Foundations of Computer Science, 14: 1007-1018.