Programmes fuzzy formal languages

Скачать 102.49 Kb.
НазваниеProgrammes fuzzy formal languages
Размер102.49 Kb.
  1   2   3   4   5   6
4th International PhD School in Formal Languages and Applications


2nd TERM



Claudio Moraga, University of Dortmund

  1. Introduction. Crisp formal languages, Chomsky hierarchy, Petri languages, Lindenmayer languages

  2. Finite fuzzy automata, fuzzy grammars, fuzzy languages. Relationship between fuzzy automata and fuzzy grammars. Fuzzy languages as families of crisp languages

  3. Crisp and fuzzy Petri nets. Crisp and fuzzy Petri languages. Peterson hierarchy of Petri languages. Evolution of fuzzy Petri languages

  4. Crisp and fuzzy L-systems. The Lindenmayer-Chomsky hierarchy. Fuzzy L-systems. Calculating the membership degree of words


Hack, M. (1975), Petri net languages, Computation Structures Group Memo 124, Project MAC, MIT.

Lindenmayer, A. (1971), Developmental systems without cellular interactions, their languages and grammars, Journal of Theoretical Biology 30: 455-484.

Meyer zu Bexten, E., F. Sajadi & C. Moraga (1997), Properties of Lindenmayer fuzzy languages and α-driven Lindenmayer languages, in Proceedings of the 27th International Symposium on Multiple–Valued Logic: 195–200. IEEE/Computer Science Press.

Mitzumoto, M, J. Toyoda & K. Tanaja (1973), Examples of formal grammars with weights, Information Processing Letters 2(4): 311-336.

Moraga, C. (2000), Towards a fuzzy computability? Mathware and Softcomputing VI(2-3): 163-172.

Peterson, J.L. (1976), Petri net Languages, Journal of Computer and System Sciences 13(1): 1-24.


Manfred Droste, University of Leipzig

Weighted automata form an exciting field using methods from theoretical computer science, algebra, and combinatorics. They have recently received much interest due to their applications in digital image compression and in natural language processing. A weighted automaton consists of a finite number of states. Actions from an alphabet can induce a change of the current state into another one (a 'transition'), and each transition carries a weight describing e.g. the resources used for its execution, the length of time needed, its reliability, or an award associated with it. Thus a weighted automaton is simply a classical non-deterministic automaton with weights associated to the transitions.

In our lectures, we will first describe how to define the behaviour of a weighted automaton. The weights are typically taken from a semiring, and the behaviour can often be described by suitable homomorphisms from the free monoid of all words over the alphabet of actions into a monoid of matrices over the given semiring –this is how algebra and combinatorics enter the scene. Then we will describe a fundamental characterization of the possible behaviours of weighted automata by rational formal power series: the Kleene-Schützenberger theorem. Afterwards, we will come to more recent research results on transformations of such behaviours, to descriptions of infinite behaviours and/or on aperiodic and star-free behaviours of weighted automata.

(Standard) References

Berstel, J. & C. Reutenauer (1988), Rational Series and Their Languages. Springer, Berlin.

Kuich, W. & A. Salomaa (1986), Semirings, Automata, Languages. Springer, Berlin.

Salomaa, A. & M. Soittola (1978), Automata-Theoretic Aspects of Formal Power Series. Springer, Berlin.

(More particular) References

Droste, M. & P. Gastin (2000), Aperiodic and star-free formal power series in partially commuting variables, in D. Krob, A.A. Mikhalev & A.V. Mikhalev, eds., Formal Power Series and Algebraic Combinatorics: 158-169. Springer, Berlin.

Droste, M. & D. Kuske (2003), Skew and infinitary formal power series, in J.C.M. Baeten, J.K. Lenstra, J. Parrow & G.J. Woeginger, eds., Automata, Languages and Programming, Lecture Notes in Computer Science 2719: 426-438. Springer, Berlin.

Droste, M. & G.-Q. Zhang (2003), On transformations of formal power series, Information and Computation 184: 369-383.


Giorgio Satta, University of Padua

  1. Introduction to context-free grammar parsing

  2. Tabular methods for context-free grammar parsing

  3. Parsing through grammar transformations (covering grammars)

  4. Parsing algorithms for mildly context-sensitive formalisms

  1   2   3   4   5   6


Programmes fuzzy formal languages iconProgrammes languages

Programmes fuzzy formal languages iconCs-300 Theory of Automata and Formal Languages

Programmes fuzzy formal languages iconCs 300 Theory of Automata and Formal Languages

Programmes fuzzy formal languages iconMore than two billion adults do not have access to formal or semi-formal financial services

Programmes fuzzy formal languages iconFuzzy Sets and Fuzzy Logic: Theory and Applications

Programmes fuzzy formal languages iconIntegrating Fuzzy Knowledge Base to Genetically Evolved Certainty Neuron Fuzzy Cognitive Maps to Facilitate Decision-Making

Programmes fuzzy formal languages icon[2] What is fuzzy logic? Что такое нечеткая логика
Используйте newsgroup comp ai fuzzy для обсуждения вопросов связанных с фази-логикой
Programmes fuzzy formal languages iconFormal Music Representation; a Case Study

Programmes fuzzy formal languages iconThe programmes of study

Programmes fuzzy formal languages iconDescription of Programmes 3

Разместите кнопку на своём сайте:

База данных защищена авторским правом © 2014
обратиться к администрации
Главная страница