Where do I/O automata, process algebras, petri nets, buchi automata, Reo, van Leeuwen-Wiederman models, cellular automata, and neural nets fall in relation to the Chomsky hierarchy? Can expressiveness results be obtained to extend the Chomsky hierarchy?
Hi!
Various models are used to capture different perspectives of the computations. As Raphael already wrote, Büchi automata are about infinite computations and so, about infinite words. Cellular automata are fully parallel devices of computations. Petri nets are used to model and analyse concurrent and distributed systems. However formal languages can also be defined by them (a word can be a sequence of transitions from an inital marking to a final marking).
I think some of the computing models used in practice (e.g. soft computing) based on probabilistic approaches, and therefore they form another branch of computing.
However, in theory when a new model is investigated, a kind of first question is about its universality (i.e. comparing it to the Turing machines, or to the 0-type generative grammars). Also it is of theoretical interest to characterise the classical language classes of the Chomsky hierarchy in various new ways...
(actualy, if you are interested a connection about Petri-nets and the Chomsky hierarchy, I have some results in B. Nagy: Graphs of Grammars – Derivations as Parallel Processes, in: Computational Intelligence in Engineering, Studies in Computational Intelligence - SCI 313, Springer (2010), 1-13. one can also represent these graphs by special Petri-nets).
- Badges
- Science topic
- Similar topics
- Computer Science