References

  1. F. Arroyo, V. Mitrana, A. Păun, M. Păun & J.R. Sánchez Couso (2020): On the group memory complexity of extended finite automata over groups. J. Log. Algebraic Methods Program. 117, pp. 100605, doi:10.1016/j.jlamp.2020.100605.
  2. B.S. Baker (1974): Non-context-free grammars generating context-free languages. Information and Control 24, pp. 231 – 246, doi:10.1016/S0019-9958(74)80038-0.
  3. J.L. Balcazar, J. Diaz & J. Gabarró (1995): Structural Complexity. Springer-Verlag, Berlin, doi:10.1007/978-3-642-79235-9.
  4. L. Boasson, B. Courcelle & M. Nivat (1981): The rational index, a complexity measure for languages. SIAM J. Computing 10, pp. 284 – 296, doi:10.1137/0210020.
  5. R.V. Book (1972): Terminal context in context-sensitive grammars. SIAM J. Computing 1, pp. 20 – 30, doi:10.1137/0201003.
  6. H. Bordihn & V. Mitrana (2020): On the degrees of non-regularity and non-context-freeness. J. Comput. Syst. Sci. 108, pp. 104 – 117, doi:10.1016/j.jcss.2019.09.003.
  7. B. Brainerd (1968): An analog of a theorem about context-free languages. Information and Control 11, pp. 561 – 567, doi:10.1016/S0019-9958(67)90771-1.
  8. N. Chomsky & M. P. Schützenberger (1963): The algebraic theory of context-free languages. In: Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam, pp. 118–161, doi:10.1016/S0049-237X(08)72023-8.
  9. J. M. Corson (2005): Extended finite automata and word problems. J. Algebra Comput. 15, pp. 455 – 466, doi:10.1142/S0218196705002360.
  10. K. Culik & H. Maurer (1978): On the Derivation of Trees. TR Vol, 18, Institut für Informationsverarbeitung (Graz).
  11. J. Dassow & G. Păun (1989): Regulated Rewriting in Formal Language Theory. Springer Berlin, Heidelberg, doi:10.1007/978-3-642-74932-2.
  12. J. Dassow & V. Mitrana (2000): Finite automata over free groups. J. Algebra Comput. 10, pp. 725 – 737, doi:10.1142/S0218196700000315.
  13. R. Evey (1963): The Theory and Application of Pushdown Store Machines. Doctoral Dissertation, Harvard University.
  14. S. Z. Fazekas, R. Mercaş & O. Wu (2022): Complexities for jumps and sweeps. Journal of Automata, Languages and Combinatorics 27, pp. 131–149, doi:10.25596/jalc-2022-131.
  15. H. Fernau & R. Stiebe (2002): Sequential grammars and automata with valences. Theoret. Comput. Sci. 276, pp. 377 – 405, doi:10.1016/S0304-3975(01)00282-1.
  16. J. Gabarro (1983): Initial index:a new complexity function for languages. In: International Colloquium on Automata, Languages, and Programming ICALP. LNCS 154 Springer Verlag, pp. 226–236, doi:10.1007/BFb0036911.
  17. J. Gabarro (1984): Pushdown space complexity and related full-A.F.L.s. In: Annual Symposium on Theoretical Aspects of Computer Science STACS. LNCS 166 Springer Verlag, pp. 250–259, doi:10.1007/3-540-12920-0_23.
  18. R. H. Gilman & M. Shapiro (1998): On groups whose word problem is solved by a nested stack automaton. arXiv:math.GR/9812028, doi:10.48550/arXiv.math/9812028.
  19. S. Ginsburg & S. Greibach (1966): Mappings which preserve context-sensitive languages. Information and Control 9, pp. 563 – 582, doi:10.1016/S0019-9958(66)80016-5.
  20. J. Goldstine (1972): Substitution and bounded languages. J. Comput. Syst. Sci. 6, pp. 9 – 29, doi:10.1016/S0022-0000(72)80038-2.
  21. T. Hibbard (1966): Scan Limited Automata and Context Limited Grammars. Doctoral Dissertation, University of California at Los Angeles.
  22. J.E. Hopcroft & J.D. Ullman (1979): Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, Mass..
  23. M. Kambites (2006): Word problems recognisable by deterministic blind monoid automata. Theoret. Comput. Sci. 362, pp. 232 – 237, doi:10.1016/j.tcs.2006.06.026.
  24. R. C. Lyndon & P. E. Schupp (1977): Combinatorial Group Theory. Springer-Verlag, Berlin, doi:10.1007/978-3-642-61896-3.
  25. C. Martín-Vide, V. Mitrana & Gh. Păun (2003): Formal Languages and Applications. Springer Verlag, doi:10.1007/978-3-540-39886-8.
  26. G. Matthews (1963): Discontinuity and asymmetry in phrase structure grammars. Information and Control 6, pp. 137–146, doi:10.1016/S0019-9958(63)90179-7.
  27. G. Matthews (1964): A note on asymmetry in phrase structure grammars. Information and Control 7, pp. 360–365, doi:10.1016/S0019-9958(64)90406-1.
  28. G. Matthews (1967): Two-way languages. Information and Control 10, pp. 111–119, doi:10.1016/S0019-9958(67)80001-9.
  29. A. Meduna & P. Zemek (2012): Jumping finite automata. Int. J. Found. Comput. Sci. 23, pp. 1555–1578, doi:10.1142/S0129054112500244.
  30. V. Mitrana & R. Stiebe (2001): Extended finite automata over groups. Discrete Appl. Math. 108, pp. 287 – 300, doi:10.1016/S0166-218X(00)00200-6.
  31. B. Nagy & L. Kovács (2014): Finite automata with translucent letters applied in natural and formal language theory. In: Transactions on Computational Collective Intelligence. LNCS 8790 Springer Verlag, pp. 107–127, doi:10.1007/978-3-662-44994-3_6.
  32. J. J. Rotman (1995): An Introduction to the Theory of Groups. Springer-Verlag, Berlin, doi:10.1007/978-1-4612-4176-8.
  33. G. Rozenberg & A. Salomaa (1997): Handbook of Formal Languages. Springer Verlag, doi:10.1007/978-3-642-59136-5.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org