docLiteraturverzeichnis - Fachgebiet Theoretische Informatik
download 
Denúncia Transcrição
Literaturverzeichnis - Fachgebiet Theoretische Informatik
Literaturverzeichnis [ABB] J.M. Autebert, J. Berstel und L. Boasson. Context-free languages and pushdown automata. In G. Rozenberg und A. Salomaa, Hrsg., Handbook of Formal Languages, Band 1, 111–174. Springer, Berlin, 1997. [AlCu] J. Albert und K. Culik. Test sets for homomorphism equivalence on context-free languages. Information and Control 45 (1980) 273–284. [Ah68] A.V. Aho. Indexed grammars – An extension of context-free grammars. Journal of the Association for Computing Machinery 15 (1968) 647–671. [Ah69] A.V. Aho. Nested stack automata. Journal of the Association for Computing Machinery 16 (1969) 383–406. [AlLa] M.H. Albert und J. Lawrence. A proof of Ehrenfeucht’s conjecture. Theoretical Computer Science 41 (1985) 121–123. [AhUl] A.V. Aho und J.D. Ullman. The Theory of Parsing, Translation, and Compiling. Prentice-Hall, Engelwood Cliffs, N.J., 1972. [Bal] M.S. Balan. Serializing the parallelism in parallel communicating pushdown automata systems. In J. Dassow, G. Pighizzini, B. Truthe (Herausg.), DCFS 2009, Proc., Electronic Proceedings in TCS 3 (2009) 59–68. [BCHV] M. ter Beek, E. Csuhaj-Varjú, M. Holzer und G. Vaszil. On competence in CD grammar systems. In C.S. Calude, E. Calude und M.J. Dinneen, Hrsg., Developments in Language Theory, Proceedings DLT 2004, Lecture Notes in Computer Science 3340, 76–88. Springer-Verlag, Berlin, 2004. [Bee] C. Beeri. An improvement on Valiant’s decision procedure for equivalence of deterministic pushdown machines. Theoretical Computer Science 3 (1976) 305–320. [Ber] J. Berstel. Transductions and Context-free Languages. Teubner Studienbücher. Teubner, Stuttgart, 1979. 569 570 LITERATURVERZEICHNIS [BoHo] H. Bordihn und M. Holzer. Random context in regulated rewriting versus cooperating distributed grammar systems. In C. Martı́nVide, F. Otto und H. Fernau (Herausg.), Language and Automata Theory and Applications, LATA 2008, Proc., Lecture Notes in Computer Science 5196, 125–136. Springer-Verlag, Berlin, 2008. [BKM03] M.S. Balan, K. Krithivasan, M. Madhu. Some variants in communication of parallel communicating pushdown automata. Journal of Automata, Languages, and Combinatorics 8 (2003) 401–416. [BKM08] H. Bordihn, M. Kutrib, A. Malcher. On the computational capacity of parallel communicating finite automata. In M. Ito and M. Toyana (Herausg.) DLT 2008, Proc., Lecture Notes in Computer Science 5257, 146–157. Springer, Berlin, 2008. [BKM10] H. Bordihn, M. Kutrib, A. Malcher. Undecidability and hierarchy results for parallel communicating finite automata. In Y. Gao, H. Lu, Sh. Seki, Sh. Yu (Herausg.) DLT 2010, Proc., Lecture Notes in Computer Science 6224, 88–99. Springer, Berlin, 2010. [BeMo] J. Berstel und M. Morcrette. Compact representation of patterns by finite automata. In A. Gagalowicz (Herausg.), Pixim 89: L’Image Numérique à Paris, 387–395, Hermes, Paris, 1989. [BoOt] R.V. Book und F. Otto. String-Rewriting Systems. Springer, New York, 1993. [BuOt] G. Buntrock und F. Otto. Growing context-sensitive languages and Church-Rosser languages. Information and Computation 141 (1998) 1–36. [Bo69] R.V. Book. Grammars with Time Functions. PhD thesis, Harvard University, Cambridge, Massachusetts, Februar 1969. [Bo82] R.V. Book. Confluent and other types of Thue systems. Journal of the Association for Computing Machinery 29 (1982) 171–182. [BPS] Y. Bar-Hillel, M. Perles und E. Shamir. On formal properties of simple phrase structure grammars. Z. Phonetik. Sprachwiss. Kommunikationsforsch. 14 (1961) 143–172. [Bra] F.J. Brandenburg. Erasing in context-free control languages. Petri nets languages make the difference. Manuscript, 1994. [Brz] J.A. Brzozowski. Canonical regular expressions and minimal state graphs for definite events. In Mathematical Theory of Automata, Vol. 12 of MRI Symposia Series, 529–561, Polytechnik Press, New York, 1962. [BS85] L. Boasson und G. Sénizergues. NTS languages are deterministic and congruential. Journal of Computer and System Sciences 31 (1985) 332–342. LITERATURVERZEICHNIS 571 [BS86] M. Benois und J. Sakarovitch. On the complexity of some extended word problems defined by cancellation rules. Information Processing Letters 23 (1986) 281–287. [Bun] G. Buntrock. Wachsende kontext-sensitive Sprachen. Habilitationsschrift, Fakultät für Mathematik und Informatik, Universität Würzburg, Juli 1996. [CaFo] P. Cartier und D. Foata. Problémes Combinatoires de Commutation et Rèarrangements. Lecture Notes in Mathematics 85, Springer, Berlin, 1969. [CsDa] E. Csuhaj-Varjú und J. Dassow. On cooperating distributed grammar systems. Journal of Information Processing and Cybernetics EIK 26 (1990) 49–63. [CDKP] E. Csuhaj-Varjú, J. Dassow, J. Kelemen und G. Păun. Grammar Systems - A Grammatical Approach to Distribution and Cooperation. Gordon and Breach, London, 1994. [CDV] E. Csuhaj-Varjú, J. Dassow und G. Vaszil. Some new models of competence-based derivations in CD grammar systems. In M. Ito und M. Toyama (Herausg.), DLT 2008, Proc., Lecture Notes in Computer Science 5257, 228–239. Springer, Berlin, 2008. [Cho56] N. Chomsky. Three models for the description of language. IRE Transactions on Information Theory 2 (1956) 113–124. [Cho59] N. Chomsky. On certain formal properties of grammars. Information and Control 2 (1959) 137–167. [Chu36] A. Church. An unsolvable problem of elementary number theory. American Journal of Mathematics 58 (1936) 345–363. (Reprinted in M. Davis. The Undecidable. Raven, New York, 1965). [CuKa] K. Culik II und J. Karhumäki. A new proof for the D0L sequence equivalence problem and its implications. In G. Rozenberg und A. Salomaa (Herausg.), The Book of L, 63–74. Springer-Verlag, Berlin, 1986. [CKM] A. Choudhary, K. Krithivasan, V. Mitrana. Returning and nonreturning parallel communicating finite automata are equivalent. RAIRO Informatique Théorique et Applications 41 (2007) 137–145. [CMMV] E. Csuhaj-Varjú, C. Martı́n-Vide, V. Mitrana, G. Vaszil. Parallel communicating pushdown automata systems. Int. Journal of Foundations of Computer Science 11 (2000) 633–650. [CrOt] R. Cremanns und F. Otto. The language of final stack contents of a pushdown automaton is effectively regular. Mathematische Schriften Kassel 11/93, Universität Kassel, September 1993. 572 LITERATURVERZEICHNIS [Coo] S.A. Cook. Characterization of pushdown machines in terms of time-bounded computers. Journal of the Association for Computing Machinery 18 (1971) 4–18. [CPV] E. Csuhaj-Varju, G. Păun, G. Vaszil. PC grammar systems with five context-free components generate all recursively enumerable languages. Theoretical Computer Science 299 (2003) 785–794. [ChSc] N. Chomsky und M.P. Schützenberger. The algebraic theory of context-free languages. In P. Bradford und D. Hirschberg (Herausg.), Computer Programming and Formal Systems, 118–161. North-Holland, Amsterdam, 1963. [CV99] E. Csuhaj-Varju, G. Vaszil. On the computational completeness of context-free parallel communicating grammar systems. Theoretical Computer Science 215 (1999) 349–358. [CV09] E. Csuhaj-Varju, G. Vaszil. On the size complexity of non-returning context-free PC grammar systems. In J. Dassow, G. Pighizzini, B. Truthe (Herausg.), DCFS 2009, Proceedings, Electronic Proceedings in TCS 3 (2009) 91–101. [Deh] M. Dehn. Über unendliche diskontinuierliche Gruppen. Mathematische Annalen 71 (1911) 116–144. [DaHr] J. Dassow und J. Hromkovic. On synchronized Lindenmayer picture languages. In G. Rozenberg und A. Salomaa (Herausg.), Lindenmayer Systems - Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology, 253–261. Springer, Berlin, 1992. [Die] V. Diekert. Makanin’s algorithm. In M. Lothair (Herausg.), Algebraic Combinatorics on Words, 387–442. Cambridge University Press, Cambridge, 2002. [DK91] J. Dassow und J. Kelemen. Cooperating/distributed grammar systems: a link between formal languages and artificial intelligence. Bulletin of the EATCS 45 (1991) 131–145. [DiRo] V. Diekert und G. Rozenberg (Herausgeber). The Book of Traces. World Scientific, Singapore, 1995. [DK99] P. Dömösi und M. Kudlek. Strong iteration lemmata for regular, linear, context-free, and linear indexed languages. In G. Ciobanu und G. Păun (Herausg.), Fundamentals of Computation Theory, Proc., Lecture Notes in Computer Science 1684, 226–233. Springer, Berlin, 1999. [DKRW] V. Diekert, M. Kufleitner, K. Reinhardt und T. Walter. Regular languages are Church-Rosser congruential. In: A. Czumaj, K. Mehlhorn, A. Pitts, R. Wattenhofer (eds.), ICALP 2012, Proc., Part II, LITERATURVERZEICHNIS 573 Lecture Notes in Computer Science 7392, 177–188. Springer, Berlin, 2012. [DaPa] J. Dassow und G. Păun. Regulated Rewriting in Formal Language Theory, EATCS Monographs on Theoretical Computer Science 18. Springer, Berlin, 1989. [DPR] J. Dassow, G. Păun und G. Rozenberg. Grammar Systems. In G. Rozenberg und A. Salomaa (Herausg.), Handbook of Formal Languages, Band 2, Linear Modelling: Background and Applications, 101–154. Springer, Berlin, Heidelberg, 1997. [DPS] J. Dassow, G. Păun und A. Salomaa. Grammars with controlled derivations. In G. Rozenberg und A. Salomaa (Herausg.), Handbook of Formal Languages, Band 2, 101–154. Springer, Berlin, 1997. [DeSc] F. Dejean und M.P. Schützenberger. On a question of Eggan. Information and Control 9 (1966) 23–25. [Dum] S. Dumitrescu. Nonreturning PC grammar sustems can be simulated by returning systems. Theoretical Computer Science 165 (1996) 463–474. [DaWa] E. Dahlhaus und M. Warmuth. Membership for growing contextsensitive grammars is polynomial. Journal of Computer and System Sciences 33 (1986) 456–472. [EsHo] K. Estenfeld und G. Hotz. Formale Sprachen. B.I., Mannheim, 1981. [Fer] H. Fernau. Unconditional transfer in regulated rewriting. Acta Informatica 34 (1997) 837–857. [Flo] R.W. Floyd. Syntactic analysis and operator precedence. Journal of the Association for Computing Machinery 10 (1963) 313–333. [FPPP] R. Freund, G. Păun, C.M. Procopiuc, O. Procopiuc. Parallel communicating grammar systems with context-sensitive components. in: G. Păun (Herausg.), Artificial Life. Grammatical Models, 166– 174. The Black Sea Univ. Press, Bucharest, 1995. [Fre] H. Freeman. On the encoding of arbitrary geometric configurations. IRE Trans. EC 10 (1961) 260–268. [GrHo] S. Greibach und J.E. Hopcroft. Independence of AFL operations. In S. Ginsburg, S. Greibach und J.E. Hopcroft (Herausg.), Studies in Abstract Families of Languages, Memoirs of the American Mathematical Society, Vol. 87. American Mathematical Society, Providence, R.I., 1969. [Gil] R.H. Gilman. A shrinking lemma for indexed languages. Theoretical Computer Science 163 (1996) 277–281. 574 LITERATURVERZEICHNIS [GaJo] M.R. Garey und D.S. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979. [Gla] A.W. Gladkij. On the complexity of derivations for context-sensitive grammars. Algebra i Logika 3 (1964) 29–44 (in Russisch). [Gre65] S.A. Greibach. A new normal form theorem for context-free phrase structure grammars. Journal of the Association for Computing Machinery 12 (1965) 42–52. [Gre67] S. Greibach. A note on pushdown store automata and regular systems. Proceedings of the American Mathematical Society 18 (1967) 263–268. [Gre68] S. Greibach. A note on undecidable properties of formal languages. Mathematical Systems Theory 2 (1968) 1–6. [Gre69] S. Greibach. An infinite hierarchy of context-free languages. Journal of the Association for Computing Machinery 16 (1969) 91–106. [Gre73] S. Greibach. The hardest context-free language. SIAM Journal on Computing 2 (1973) 304–310. [Gri] Th. Griffiths. Some remarks on derivations in general rewriting systems. Information and Control 12 (1968) 27–54. [Gub] V.S. Guba. Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems. Matematicheskie Zametki 40 (1086) 321–324 (in Russisch). [GiSp] S. Ginsburg und E. Spanier. Finite-turn pushdown automata. SIAM Journal on Control 4 (1966) 429–453. [Har] M. Harrison. Introduction to Formal Language Theory. AddisonWesley, Reading, M.A., 1978. [Has] K. Hashiguchi. Algorithms for determining relative star height and star height. Information and Computation 78 (1988) 124–169. [Hea] T. Head. Formal languages and DNA: an analysis of the generative capacity of specific recombinant behaviors. Bulletin of Mathematical Biology 49 (1987) 737–759. [HHI] J. Hartmanis und H.B. Hunt III. The LBA problem and its importance in the theory of computing. In R.M. Karp (Herausg.), Complexity of Computation, 1–26. American Mathematical Society, Providence, R.I., 1974. [HaJa] D. Hauschildt und M. Jantzen. Petri net algorithms in the theory of matrix grammars. Acta Informatica 31 (1994) 719–728. LITERATURVERZEICHNIS 575 [HePi] R. Herschel und F. Pieper, Hrsg., PASCAL – Systematische Darstellung von PASCAL und CONCURRENT PASCAL für den Anwender. Oldenbourg, München, 1979. [HoUl] J.E. Hopcroft und J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, M.A., 1979. [Iba74] O. Ibarra. A note on semilinear sets and bounded-reversal multihead pushdown automata. Information Processing Letters 3 (1974) 25–28. [Iba78] O. Ibarra. Reversal-bounded multicounter machines and their decision problems. Journal of the Association for Computing Machinery 25 (1978) 116–133. [Imm] N. Immerman. Languages that capture complexity classes. SIAM Journal on Computing 16 (1987) 760–778. [Jaf] J. Jaffe. A necessary and sufficient pumping lemma for regular languages. SIGACT News 10 (1978) 48–49. [JuLo] T. Jurdziński und K. Loryś. Church-Rosser languages vs. UCFL. In P. Widmayer, F. Triguero, R. Morales, M. Hennessy, S. Eidenbenz und R. Conejo (Herausg.), Proc. of 29rd ICALP, Lecture Notes in Computer Science 2380, 147–158. Springer, Berlin, 2002. [JLNO] T. Jurdziński, K. Loryś, G. Niemann und F. Otto. Some results on RWW- and RRWW-automata and their relation to the class of growing context-sensitive languages. Journal of Automata, Languages, and Combinatorics 9 (2004) 407–437. [JMPV99] P. Jančar, F. Mráz, M. Plátek und J. Vogel. On monotonic automata with a restart operation. Journal of Automata, Languages, and Combinatorics 4 (1999) 287–311. [JMPV04] P. Jančar, F. Mráz, M. Plátek und J. Vogel. Monotonicity of restarting automata. Journal of Automata, Languages, and Combinatorics 12 (2007) 355–371. [JOMP] T. Jurdziński, F. Otto, F. Mráz und M. Plátek. On the complexity of 2-monotone restarting automata. Theory of Computing Systems 42 (2008) 488–518. [JeWi] K. Jensen und N. Wirth. Pascal - User Manual and Report. 3. Edition, Springer, New York, 1985. [Kar] J. Karhumäki. On the equivalence problem for binary D0L-systems. Information and Control 50 (1981) 276–284. 576 LITERATURVERZEICHNIS [Kas] T. Kasami. An efficient recognition and syntax algorithm for context-free languages. Scientific report afcrl-65-758, Air Force Cambridge Research Lab., Bedford, Mass., 1965. [KKMN] D. Kapur, M. Krishnamoorthy, R. McNaughton und P. Narendran. An O(|T |3 ) algorithm for testing the Church-Rosser property of Thue systems. Theoretical Computer Science 35 (1985) 109–114. [Kle] S.C. Kleene. Representation of events in nerve nets and finite automata. In C.E. Shannon und M. McCarthy (Herausg.), Automata Studies, Annals of Math. Studies 34, 3–41. Princeton University Press, Princeton, N.J., 1956. [KMO10] M. Kutrib, H. Messerschmidt und F. Otto. On stateless twopushdown automata and restarting automata. Int. Journal of Foundations of Computer Science 21 (2010) 781–798. [KMO10a] M. Kutrib, H. Messerschmidt und F. Otto. On stateless deterministic restarting automata. Acta Informatica 47 (2010) 391–412. [KMP] D.E. Knuth, J.H. Morris und V.R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing 6 (1977) 323–350. [Koz] D. Kozen. Lower bounds for natural proof systems. In Proc. of 18th FOCS, 254–266. IEEE Computer Society Press, 1977. [KRS] L. Kari, G. Rozenberg, und A. Salomaa. L-Systems. In G. Rozenberg und A. Salomaa (Herausg.), Handbook of Formal Languages, Vol. 1: Word, Language, Grammar. Springer, Berlin, 1997. [Lau] C. Lautemann. One pushdown and a small tape. In K.W. Wagner (Herausg.), Dirk Siefkes zum 50. Geburtstag, 42–47. Technische Universität Berlin und Universität Augsburg, 1988. [Lin] A. Lindenmayer. Mathematical models for cellular interactions in development, I and II. J. Theoret. Biology 18 (1968) 280–315. [Mak] G.S. Makanin. The problem of solvability of equations in a free semigroup. Matematicheskiı̆ Sbornik 103 (1977) 147–236. Engl. Übersetzung in Math. SSSR Sbornik 32 (1977) 129–198. [Man] N. Mandache. On the computational power of context-free PC grammer systems. Theoretical Computer Science 237 (2000) 135– 148. [Mar69] S. Marcus. Contextual grammars. Rev. Roumaine Math. Pures Appl. 14 (1969) 1525–1534. [Mar77] G. Markowsky. Bounds on the index and period of a binary relation on a finite set. Semigroup Forum 13 (1977) 253–259. LITERATURVERZEICHNIS 577 [Maz] A. Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. PB78, Aarhus University, Aarhus, 1977. [McN] R. McNaughton. Algebraic decision procedures for local testability. Mathematical Systems Theory 8 (1974) 60–76. [Mea] G.H. Mealy. A method for synthesizing sequential circuits. Bell System Technical J. 34 (1955) 1045–1079. [MeSt] H. Messerschmidt, H. Stamer. Restart-Automaten mit mehreren Restart-Zuständen. In H. Bordihn (Herausg.), Workshop “Formale Methoden in der Linguistik” und 14. Theorietag “Automaten und Formale Sprachen, 111–116. Institut für Informatik, Universität Potsdam, 2004. [MMM] C. Martı́n-Vide, A. Mateescu, V. Mitrana. Parallel finite automata systems communicating by states. Int. Journal of Foundations of Computer Science 13 (2002) 733–749. [MNO] R. McNaughton, P. Narendran, F. Otto. Church-Rosser Thue systems and formal languages. Journal of the Association for Computing Machinery 35 (1988) 324–344. [Moo] E.F. Moore. Gedanken experiments on sequential machines. In Automata Studies, 129–153. Priceton Univ. Press, Princeton, N.J., 1966. [Mrá] F. Mráz. Lookahead hierarchies of restarting automata. Journal of Automata, Languages, and Combinatorics 6 (2001) 493–506. [MO03] F. Mráz und F. Otto. Hierarchies of weakly monotone restarting automata. RAIRO Informatique Théorique et Applications 39 (2005) 325–342. [MO07] H. Messerschmidt und F. Otto. Cooperating distributed systems of restarting automata. Int. Journal of Foundations of Computer Science 18 (2007) 1333–1342. [MO09] H. Messerschmidt und F. Otto. On deterministic CD-systems of restarting automata. Int. Journal of Foundations of Computer Science 20 (2009) 185–209. [MOPJ] F. Mráz, F. Otto, M. Plátek und T. Jurdziński. Marcus t-contextual grammars and cut hierarchies and monotonicity for restarting automata. Theoretical Computer Science 366 (2006) 272–296. [MPP99] F. Mráz, M. Plátek und M. Procházka. On special forms of restarting automata. Grammars 2 (1999) 223–233. [MPP00] F. Mráz, M. Plátek und M. Procházka. Restarting automata, deleting, and Marcus grammars. In C. Martı́n-Vide und G. Păun 578 LITERATURVERZEICHNIS (Herausg.), Recent Topics in Mathematical and Computational Linguistics, 218–233. Editura Academiei Române, Bukarest, 2000. [MRW82] H.A. Maurer, G. Rozenberg, und E. Welzl. Using string languages to describe picture languages. Information and Control, 54:155– 185, 1982. [MeSt] A.R. Meyer und L.J. Stockmeyer. Word problems requiring exponential time: preliminary report. In Proc. of 5th STOC, 1–9. ACM Press, 1973. [NO11] B. Nagy und F. Otto. Globally deterministic CD-Systems of stateless R(1)-automata. In A. H. Dediu, S. Inenaga und C. MartinVide (Herausgeber), LATA 2011, Proc., Lecture Notes in Computer Science 6638, 390–401. Springer, Berlin, 2011. [NO11a] B. Nagy und F. Otto. CD-systems of stateless deterministic R(1)automata governed by an external pushdown store. RAIRO Informatique Théorique et Applications 45 (2011) 413–448. [NO12] B. Nagy und F. Otto. On CD-systems of stateless deterministic Rautomata with window size one. Journal of Computer and System Sciences 78 (2012) 780–806. [Nar] P. Narendran. Church-Rosser and Related Thue Systems. PhD dissertation, Rensselaer Polytechnic Institute, Troy, N.Y., 1984. [Nie00] G. Niemann. Regular Languages and Church-Rosser congruential languages. In: R. Freund, A. Kelemenova (eds.), International Workshop “Grammar Systems 2000”, Proc., Silesian University of Opava, Faculty of Philosophy and Science, Institute of Computer Science, 2000, 359–370. [Nie02] G. Niemann. Church-Rosser Languages and Related Classes. Dissertation, Fachbereich Mathematik/Informatik, Universität Kassel, 2002. [Niv] M. Nivat. Transductions des langages de Chomsky. Annales de l’Institut Fourier, Grenoble 18 (1968) 339–456. [NiWa] G. Niemann, J. Waldmann. Some regular languages that are Church-Rosser congruential. In: W. Kuich, G. Rozenberg, A. Salomaa (eds.), DLT 2001, Proc., Lecture Notes in Computer Science 2295, 330–339. Springer, Berlin, 2002. [NiOt] G. Niemann und F. Otto. Further results on restarting automata. In M. Ito und T. Imaoka (Herausg.), Words, Languages and Combinatorics III, Proc., 352–369, World Scientific, Singapore, 2003. [NiWo] G. Niemann und J.R. Woinowski. The growing context-sensitive languages are the acyclic context-sensitive languages. In W. Kuich, LITERATURVERZEICHNIS 579 G. Rozenberg und A. Salomaa (Herausg.), DLT 2001, Proc., Lecture Notes in Computer Science 2295, 197–205. Springer, Berlin, 2002. [Ogd] W. Ogden. A helpful result for proving inherent ambiguity. Mathematical Systems Theory 2 (1968) 191–194. [OtJu] F. Otto und T. Jurdziński. On left-monotone restarting automata. Mathematische Schriften Kassel 17/03, Universität Kassel, November 2003. [OKK] F. Otto, M. Katsura und Y. Kobayashi. Infinite convergent stringrewriting systems and cross-sections for finitely presented monoids. Journal of Symbolic Computation 26 (1998) 621–648. [Ott] F. Otto. On centralized PC grammar systems with context-sensitive components. In H.C. Yen and O.H. Ibarra (Herausg.), DLT 2012, Proc., Lecture Notes in Computer Science 7410, 356–367. Springer, Berlin, 2012. [Par] R.J. Parikh. Language-generating devices. Quarterly Progress Report, No. 60, Research Laboratory of Electronics, M.I.I., 199–212, 1961. [Pă97] G. Păun. Marcus Contextual Grammars, Studies in Linguistics and Philosophy, Band 67. Kluwer Academic Publishers, Dordrecht, 1997. [Pă99] G. Păun. Computing with membranes. An introduction. Bulletin of the EATCS 67 (1999) 139–152. [Pin] J. Pin. Syntactic semigroups. In: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal languages, Vol. 1, 679–746. Springer, Berlin, 1997. [PIT] O. Procopiuc, C.M. Ionescu, F.L. Tiplea. Parallel communicating grammar systems: the context-sensitive case. Int. Journal of Computer Mathematics 49 (1993) 145–156. [Plá00] M. Plátek. Weak cyclic forms of restarting automata. In G. Rozenberg und W. Thomas (Herausg.), DLT’99: Developments in Language Theory, Proc., 115–124. World Scientific, Singapore, 2000. [Plá01] M. Plátek. Two-way restarting automata and j-monotonicity. In L. Pacholski und P. Ružička (Herausg.), SOFSEM 2001: Theory and Practice of Informatics, Proc., Lecture Notes in Computer Science 2234, 316–325. Springer, Berlin, 2001. [PLO] M. Plátek, M. Lopatková und K. Oliva. Restarting automata: motivations and applications. In M. Holzer (Herausg.), Workshop “Petrinets” und 13. Theorietag “Automaten und Formale Sprachen, 580 LITERATURVERZEICHNIS 90–96, Institut für Informatik, Technische Universität München, Garching, 2003. [POMJ] M. Plátek, F. Otto, F. Mráz und T. Jurdziński. Restarting automata and variants of j-monotonicity. Mathematische Schriften Kassel 9/03, Universität Kassel, Oktober 2003. [Po36] E. Post. Finite combinatory processes-formulation. The Journal of Symbolic Logic 1 (1936) 103–105. [Po46] E. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society 52 (1946) 264–268. [Ric] H.G. Rice. Classes of recursively enumerable sets and their decision problems. Transaction of the American Mathematical Society 89 (1953) 25–59. [Ro66] A.L. Rosenberg. On multi-head finite automata. IBM J. Research Development 10 (1966) 388–394. [Ro67] D.J. Rosenkrantz. Matrix equations and normal forms for contextfree grammars. Journal of the Association for Computing Machinery 14 (1967) 501–507. [Ro69] D.J. Rosenkrantz. Programmed grammars and classes of formal languages. Journal of the Association for Computing Machinery 16 (1969) 107–131. [RS80] G. Rozenberg und A. Salomaa. The Mathematical Theory of L Systems. Academic Press, New York, 1980. [RS97] G. Rozenberg und A. Salomaa (Herausg.), Handbook of Formal Languages, Band 1. Word, Language, Grammar. Springer, Berlin, 1997. [RS97a] G. Rozenberg und A. Salomaa (Herausg.), Handbook of Formal Languages, Band 2. Linear Modeling: Background and Application. Springer, Berlin, 1997. [Sa73] A. Salomaa. Formal Languages. Academic Press, New York, 1973. [Sa78] A. Salomaa. Formale Sprachen. Berlin, 1978. [Sch92] K.U. Schulz. Makanin’s algorithm for word equations: Two improvements and a generalization. In K.U. Schulz (Herausg.), Word Equations an Related Topics, IWWERT’90, Proceedings, Lecture Notes in Computer Science 572, 85–150. Springer, Berlin, 1992. [Sch01] U. Schöning. Theoretische Informatik - kurzgefasst, 4. Aufl. Spektrum Akademischer Verlag, Heidelberg, 2001.
