{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T08:21:47Z","timestamp":1777105307813,"version":"3.51.4"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:p>In procedural programming languages, the order of executing the statements may follow a regular pattern, including sequences of statements, conditional and branching statements and loops. On the other hand, regular languages can be represented by finite state acceptors (finite automata), by regular expressions and by (a special form of) railroad diagrams (syntax diagrams) allowing alternatives, option, concatenation and iteration. Context-free languages can also be described by (the general form of) railroad diagrams allowing also recursion. Based on the analogy of finite automata and railroad diagrams, the transformation between node-labelled and edge-labelled graphs, special infinite state automata, namely the fractal automata, are established to characterize the class of context-free languages. Deterministic and linear variants are also investigated. To establish these connections, we also define such variants of pushdown automata that accept the deterministic context-free and linear languages by empty stack. A transformation between the pushdown automata and fractal automata is also shown. The proposed model gives some new insights and a new view of context-free languages, deterministic context-free languages, linear context-free and deterministic linear context-free languages.<\/jats:p>","DOI":"10.1142\/s0129054125450017","type":"journal-article","created":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T05:37:07Z","timestamp":1742276227000},"page":"1117-1148","source":"Crossref","is-referenced-by-count":1,"title":["Fractal Automata: Recursion in Context-Free and in Deterministic and Linear Context-Free Languages"],"prefix":"10.1142","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9494-6440","authenticated-orcid":false,"given":"Benedek","family":"Nagy","sequence":"first","affiliation":[{"name":"Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, Famagusta, North Cyprus, Mersin-10, Turkey"},{"name":"Department of Computer Science, Institute of Mathematics and Informatics, Eszterh\u00e1zy K\u00e1roly Catholic University, Eger, Hungary"}]}],"member":"219","published-online":{"date-parts":[[2025,3,18]]},"reference":[{"key":"S0129054125450017BIB001","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho A. V.","year":"2006","edition":"2"},{"key":"S0129054125450017BIB002","series-title":"UNESCO","first-page":"125","volume-title":"Proceedings of the International Conference on Information Processing","author":"Backus J. W.","year":"1959"},{"key":"S0129054125450017BIB003","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1956.1056813"},{"key":"S0129054125450017BIB004","doi-asserted-by":"publisher","DOI":"10.1109\/ICSMC.2001.973505"},{"key":"S0129054125450017BIB006","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321254"},{"key":"S0129054125450017BIB007","volume-title":"Introduction to Formal Language Theory","author":"Harrison M. A.","year":"1978"},{"key":"S0129054125450017BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-33636-3_5"},{"key":"S0129054125450017BIB009","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S0129054125450017BIB010","volume-title":"Fundamentals of Programming Languages","author":"Horowitz E.","year":"2012"},{"key":"S0129054125450017BIB011","first-page":"194","volume":"2","author":"Horv\u00e1th G.","year":"2010","journal-title":"Acta Univ. Sapientiae, Informatica"},{"key":"S0129054125450017BIB013","series-title":"Supplemental Material (CDMTCS-252 report)","first-page":"10","volume-title":"DLT\u201904, Eighth International Conference on Developments in Language Theory","author":"Nagy B.","year":"2004"},{"key":"S0129054125450017BIB014","first-page":"6","volume-title":"e-Proc. of IF 2005: Conf. Inform. Higher Educ.","author":"Nagy B.","year":"2005"},{"key":"S0129054125450017BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44043-8_7"},{"key":"S0129054125450017BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-13502-6_8"},{"key":"S0129054125450017BIB018","volume-title":"Handbook of Automata Theory","volume":"2","author":"Pin J.-E.","year":"2021"},{"key":"S0129054125450017BIB019","volume-title":"Introduction to Formal Languages","author":"R\u00e9v\u00e9sz Gy. E.","year":"1983"},{"key":"S0129054125450017BIB020","doi-asserted-by":"publisher","DOI":"10.1142\/3303"},{"key":"S0129054125450017BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6"},{"key":"S0129054125450017BIB022","volume-title":"Models of Computation: Exploring the Power of Computing","author":"Savage J. E.","year":"1998"},{"key":"S0129054125450017BIB023","volume-title":"Programming Languages: Principles and Paradigms","author":"Tucker A.","year":"2002"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054125450017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T08:17:10Z","timestamp":1762503430000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054125450017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,18]]},"references-count":20,"journal-issue":{"issue":"07","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["10.1142\/S0129054125450017"],"URL":"https:\/\/doi.org\/10.1142\/s0129054125450017","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,18]]}}}