{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T04:14:11Z","timestamp":1754194451462,"version":"3.40.3"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030232467"},{"type":"electronic","value":"9783030232474"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-23247-4_4","type":"book-chapter","created":{"date-parts":[[2019,7,7]],"date-time":"2019-07-07T23:02:38Z","timestamp":1562540558000},"page":"57-73","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Limited Automata: Properties, Complexity and Variants"],"prefix":"10.1007","author":[{"given":"Giovanni","family":"Pighizzini","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,25]]},"reference":[{"issue":"3","key":"4_CR1","doi-asserted-by":"publisher","first-page":"16:1","DOI":"10.1145\/1516512.1516518","volume":"56","author":"R Alur","year":"2009","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56(3), 16:1\u201316:43 (2009). https:\/\/doi.org\/10.1145\/1516512.1516518","journal-title":"J. ACM"},{"key":"4_CR2","doi-asserted-by":"publisher","unstructured":"Chomsky, N., Sch\u00fctzenberger, M.: The algebraic theory of context-free languages. In: Braffort, P., Hirschberg, D. (eds.) Computer Programming and Formal Systems, Studies in Logic and the Foundations of Mathematics, vol. 35, pp. 118\u2013161. Elsevier (1963). https:\/\/doi.org\/10.1016\/S0049-237X(08)72023-8","DOI":"10.1016\/S0049-237X(08)72023-8"},{"issue":"3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M Chrobak","year":"1986","unstructured":"Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci. 47(3), 149\u2013158 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90142-8. Errata: 302(1\u20133), 497\u2013498 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"4_CR4","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/321127.321132","volume":"9","author":"S Ginsburg","year":"1962","unstructured":"Ginsburg, S., Rice, H.G.: Two families of languages related to ALGOL. J. ACM 9(3), 350\u2013371 (1962). https:\/\/doi.org\/10.1145\/321127.321132","journal-title":"J. ACM"},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-319-98654-8_30","volume-title":"Developments in Language Theory","author":"B Guillon","year":"2018","unstructured":"Guillon, B., Pighizzini, G., Prigioniero, L., Pr\u016f\u0161a, D.: Two-way automata and one-tape machines. In: Hoshi, M., Seki, S. (eds.) DLT 2018. LNCS, vol. 11088, pp. 366\u2013378. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98654-8_30"},{"key":"4_CR6","doi-asserted-by":"publisher","unstructured":"Guillon, B., Prigioniero, L.: Linear-time limited automata. Theoret. Comput. Sci. (2019, in press). https:\/\/doi.org\/10.1016\/j.tcs.2019.03.037","DOI":"10.1016\/j.tcs.2019.03.037"},{"issue":"2","key":"4_CR7","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.ic.2005.05.005","volume":"203","author":"LA Hemaspaandra","year":"2005","unstructured":"Hemaspaandra, L.A., Mukherji, P., Tantau, T.: Context-free languages can be accepted with absolutely no space overhead. Inform. Comput. 203(2), 163\u2013180 (2005). https:\/\/doi.org\/10.1016\/j.ic.2005.05.005","journal-title":"Inform. Comput."},{"issue":"6","key":"4_CR8","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","volume":"8","author":"FC Hennie","year":"1965","unstructured":"Hennie, F.C.: One-tape, off-line Turing machine computations. Inf. Control 8(6), 553\u2013578 (1965)","journal-title":"Inf. Control"},{"issue":"1\/2","key":"4_CR9","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/S0019-9958(67)90513-X","volume":"11","author":"TN Hibbard","year":"1967","unstructured":"Hibbard, T.N.: A generalization of context-free determinism. Inf. Control 11(1\/2), 196\u2013238 (1967)","journal-title":"Inf. Control"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/3-540-55808-X_29","volume-title":"Mathematical Foundations of Computer Science 1992","author":"P Jan\u010dar","year":"1992","unstructured":"Jan\u010dar, P., Mr\u00e1z, F., Pl\u00e1tek, M.: Characterization of context-free languages by erasing automata. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol. 629, pp. 307\u2013314. Springer, Heidelberg (1992). https:\/\/doi.org\/10.1007\/3-540-55808-X_29"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/3-540-57182-5_44","volume-title":"Mathematical Foundations of Computer Science 1993","author":"P Jancar","year":"1993","unstructured":"Jancar, P., Mr\u00e1z, F., Pl\u00e1tek, M.: A taxonomy of forgetting automata. In: Borzyszkowski, A.M., Soko\u0142owski, S. (eds.) MFCS 1993. LNCS, vol. 711, pp. 527\u2013536. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-57182-5_44"},{"issue":"5","key":"4_CR12","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s002360050050","volume":"33","author":"P Jan\u010dar","year":"1996","unstructured":"Jan\u010dar, P., Mr\u00e1z, F., Pl\u00e1tek, M.: Forgetting automata and context-free languages. Acta Inform. 33(5), 409\u2013420 (1996). https:\/\/doi.org\/10.1007\/s002360050050","journal-title":"Acta Inform."},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/3-540-60249-6_60","volume-title":"Fundamentals of Computation Theory","author":"P Jan\u010dar","year":"1995","unstructured":"Jan\u010dar, P., Mr\u00e1z, F., Pl\u00e1tek, M., Vogel, J.: Restarting automata. In: Reichel, H. (ed.) FCT 1995. LNCS, vol. 965, pp. 283\u2013292. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60249-6_60"},{"issue":"2","key":"4_CR14","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2017.09.005","volume":"259","author":"M Kutrib","year":"2018","unstructured":"Kutrib, M., Pighizzini, G., Wendlandt, M.: Descriptional complexity of limited automata. Inform. Comput. 259(2), 259\u2013276 (2018). https:\/\/doi.org\/10.1016\/j.ic.2017.09.005","journal-title":"Inform. Comput."},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-319-19225-3_13","volume-title":"Descriptional Complexity of Formal Systems","author":"M Kutrib","year":"2015","unstructured":"Kutrib, M., Wendlandt, M.: On simulation cost of unary limited automata. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 153\u2013164. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-19225-3_13"},{"issue":"1\u20132","key":"4_CR16","doi-asserted-by":"publisher","first-page":"31","DOI":"10.3233\/FI-2017-1575","volume":"155","author":"M Kutrib","year":"2017","unstructured":"Kutrib, M., Wendlandt, M.: Reversible limited automata. Fund. Inform. 155(1\u20132), 31\u201358 (2017). https:\/\/doi.org\/10.3233\/FI-2017-1575","journal-title":"Fund. Inform."},{"key":"4_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/3-540-10003-2_89","volume-title":"Automata, Languages and Programming","author":"K Mehlhorn","year":"1980","unstructured":"Mehlhorn, K.: Pebbling mountain ranges and its application to DCFL-recognition. In: de Bakker, J., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 422\u2013435. Springer, Heidelberg (1980). https:\/\/doi.org\/10.1007\/3-540-10003-2_89"},{"issue":"2","key":"4_CR18","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/BF01068368","volume":"27","author":"IR Nasyrov","year":"1991","unstructured":"Nasyrov, I.R.: Deterministic realization of nondeterministic computations with a low measure of nondeterminism. Cybernetics 27(2), 170\u2013179 (1991). https:\/\/doi.org\/10.1007\/BF01068368","journal-title":"Cybernetics"},{"issue":"2","key":"4_CR19","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0214031","volume":"14","author":"WF Ogden","year":"1985","unstructured":"Ogden, W.F., Ross, R.J., Winklmann, K.: An \u201cinterchange lemma\u201d for context-free languages. SIAM J. Comput. 14(2), 410\u2013415 (1985). https:\/\/doi.org\/10.1137\/0214031","journal-title":"SIAM J. Comput."},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-642-31653-1_12","volume-title":"Developments in Language Theory","author":"A Okhotin","year":"2012","unstructured":"Okhotin, A.: Non-erasing variants of the Chomsky\u2013Sch\u00fctzenberger theorem. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol. 7410, pp. 121\u2013129. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31653-1_12"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-45007-6_5","volume-title":"Developments in Language Theory","author":"F Otto","year":"2003","unstructured":"Otto, F.: Restarting automata and their relations to the Chomsky hierarchy. In: \u00c9sik, Z., F\u00fcl\u00f6p, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 55\u201374. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45007-6_5"},{"key":"4_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/3-540-08353-7_164","volume-title":"Mathematical Foundations of Computer Science 1977","author":"J Peckel","year":"1977","unstructured":"Peckel, J.: On a deterministic subclass of context-free languages. In: Gruska, J. (ed.) MFCS 1977. LNCS, vol. 53, pp. 430\u2013434. Springer, Heidelberg (1977). https:\/\/doi.org\/10.1007\/3-540-08353-7_164"},{"issue":"1","key":"4_CR23","doi-asserted-by":"publisher","first-page":"43","DOI":"10.21136\/CPM.1978.117969","volume":"103","author":"J Peckel","year":"1978","unstructured":"Peckel, J.: A deterministic subclass of context-free languages. \u010casopis pro p\u011bstov\u00e1n\u00ed matematiky 103(1), 43\u201352 (1978). http:\/\/eudml.org\/doc\/21335","journal-title":"\u010casopis pro p\u011bstov\u00e1n\u00ed matematiky"},{"key":"4_CR24","doi-asserted-by":"publisher","unstructured":"Pighizzini, G.: Nondeterministic one-tape off-line Turing machines. J. Autom. Lang. Comb. 14(1), 107\u2013124 (2009). https:\/\/doi.org\/10.25596\/jalc-2009-107. http:\/\/arXiv.org\/abs\/0905.1271","DOI":"10.25596\/jalc-2009-107"},{"issue":"2\u20133","key":"4_CR25","doi-asserted-by":"publisher","first-page":"225","DOI":"10.3233\/FI-2013-879","volume":"126","author":"G Pighizzini","year":"2013","unstructured":"Pighizzini, G.: Two-way finite automata: old and recent results. Fund. Inform. 126(2\u20133), 225\u2013246 (2013). https:\/\/doi.org\/10.3233\/FI-2013-879","journal-title":"Fund. Inform."},{"issue":"3","key":"4_CR26","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/2818936.2818947","volume":"46","author":"G Pighizzini","year":"2015","unstructured":"Pighizzini, G.: Guest column: one-tape Turing machine variants and language recognition. SIGACT News 46(3), 37\u201355 (2015). https:\/\/doi.org\/10.1145\/2818936.2818947","journal-title":"SIGACT News"},{"issue":"3\u20134","key":"4_CR27","doi-asserted-by":"publisher","first-page":"369","DOI":"10.3233\/FI-2016-1439","volume":"148","author":"G Pighizzini","year":"2016","unstructured":"Pighizzini, G.: Strongly limited automata. Fund. Inform. 148(3\u20134), 369\u2013392 (2016). https:\/\/doi.org\/10.3233\/FI-2016-1439","journal-title":"Fund. Inform."},{"issue":"7","key":"4_CR28","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1142\/S0129054114400140","volume":"25","author":"G Pighizzini","year":"2014","unstructured":"Pighizzini, G., Pisoni, A.: Limited automata and regular languages. Internat. J. Found. Comput. Sci. 25(7), 897\u2013916 (2014). https:\/\/doi.org\/10.1142\/S0129054114400140","journal-title":"Internat. J. Found. Comput. Sci."},{"issue":"1\u20132","key":"4_CR29","doi-asserted-by":"publisher","first-page":"157","DOI":"10.3233\/FI-2015-1148","volume":"136","author":"G Pighizzini","year":"2015","unstructured":"Pighizzini, G., Pisoni, A.: Limited automata and context-free languages. Fund. Inform. 136(1\u20132), 157\u2013176 (2015). https:\/\/doi.org\/10.3233\/FI-2015-1148","journal-title":"Fund. Inform."},{"key":"4_CR30","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.ic.2019.01.002","volume":"266","author":"G Pighizzini","year":"2019","unstructured":"Pighizzini, G., Prigioniero, L.: Limited automata and unary languages. Inform. Comput. 266, 60\u201374 (2019). https:\/\/doi.org\/10.1016\/j.ic.2019.01.002","journal-title":"Inform. Comput."},{"key":"4_CR31","doi-asserted-by":"publisher","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two way finite automata. In: Lipton, R.J., Burkhard, W.A., Savitch, W.J., Friedman, E.P., Aho, A.V. (eds.) Proceedings 10th Annual ACM Symposium on Theory of Computing (STOC 1978), pp. 275\u2013286. ACM (1978). https:\/\/doi.org\/10.1145\/800133.804357","DOI":"10.1145\/800133.804357"},{"issue":"2","key":"4_CR32","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"JC Shepherdson","year":"1959","unstructured":"Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3(2), 198\u2013200 (1959). https:\/\/doi.org\/10.1147\/rd.32.0198","journal-title":"IBM J. Res. Dev."},{"key":"4_CR33","unstructured":"Sloane, N.J.A.: The on-line encyclopedia of integer sequences. http:\/\/oeis.org\/A007814"},{"key":"4_CR34","volume-title":"Computational Complexity","author":"KW Wagner","year":"1986","unstructured":"Wagner, K.W., Wechsung, G.: Computational Complexity. D. Reidel Publishing Company, Dordrecht (1986)"},{"key":"4_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/3-540-07389-2_233","volume-title":"Mathematical Foundations of Computer Science 1975 4th Symposium, Mari\u00e1nsk\u00e9 L\u00e1zn\u011b, September 1\u20135, 1975","author":"G Wechsung","year":"1975","unstructured":"Wechsung, G.: Characterization of some classes of context-free languages in terms of complexity classes. In: Be\u010dv\u00e1\u0159, J. (ed.) MFCS 1975. LNCS, vol. 32, pp. 457\u2013461. Springer, Heidelberg (1975). https:\/\/doi.org\/10.1007\/3-540-07389-2_233"},{"key":"4_CR36","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(79)90010-0","volume":"9","author":"G Wechsung","year":"1979","unstructured":"Wechsung, G., Brandst\u00e4dt, A.: A relation between space, return and dual return complexities. Theoret. Comput. Sci. 9, 127\u2013140 (1979). https:\/\/doi.org\/10.1016\/0304-3975(79)90010-0","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/978-3-030-10801-4_40","volume-title":"SOFSEM 2019: Theory and Practice of Computer Science","author":"T Yamakami","year":"2019","unstructured":"Yamakami, T.: Behavioral strengths and weaknesses of various models of limited automata. In: Catania, B., Kr\u00e1lovi\u010d, R., Nawrocki, J., Pighizzini, G. (eds.) SOFSEM 2019. LNCS, vol. 11376, pp. 519\u2013530. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-10801-4_40"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-23247-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T06:51:10Z","timestamp":1739343070000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-23247-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030232467","9783030232474"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-23247-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"25 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DCFS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Descriptional Complexity of Formal Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ko\u0161ice","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dcfs2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/im.saske.sk\/dcfs2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"18","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"72% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3,1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2,9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"there are also 4 invited talks","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}