{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T03:13:45Z","timestamp":1649042025143},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:p> We bring into attention the interplay between model theory of committed graphs (1-regular graphs) and their palindromic characteristic in the domain of formal languages. We prove some model theoretic properties of committed graphs and then give a characterization of them in the formal language domain using palindromes. We show in the first part of the paper that the theory of committed graphs and the theory of infinite committed graphs differ in terms of completeness. We give the observation that theories of finite and infinite committed graphs are both decidable. The former is finitely axiomatizable, whereas the latter is not. We note that every committed graph is isomorphic to the structure of integers. In the second part, as our main focus of the paper and using some of the results in the first section, we give a characterization of committed graphs based on the notion of finite and infinite palindrome strings. <\/jats:p>","DOI":"10.1142\/s0129054120500203","type":"journal-article","created":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T11:46:20Z","timestamp":1594035980000},"page":"483-498","source":"Crossref","is-referenced-by-count":0,"title":["Palindromic Characteristic of Committed Graphs and Some Model Theoretic Properties"],"prefix":"10.1142","volume":"31","author":[{"given":"Ahmet","family":"\u00c7evik","sequence":"first","affiliation":[{"name":"Gendarmerie and Coast Guard Academy, 06805 Beytepe, \u00c7ankaya, Ankara, Turkey"}]}],"member":"219","published-online":{"date-parts":[[2020,7,6]]},"reference":[{"key":"S0129054120500203BIB001","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410400242X"},{"key":"S0129054120500203BIB002","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/044\/1141922"},{"key":"S0129054120500203BIB003","doi-asserted-by":"publisher","DOI":"10.14232\/actacyb.22.3.2016.10"},{"key":"S0129054120500203BIB004","first-page":"19:1","volume-title":"27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)","author":"Geizhals S. H.","year":"2016"},{"issue":"8","key":"S0129054120500203BIB005","first-page":"441","volume":"23","author":"Horv\u00e1th S.","year":"1987","journal-title":"J. Inform. Process. Cybernet."},{"key":"S0129054120500203BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-53733-7_11"},{"key":"S0129054120500203BIB007","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559807"},{"key":"S0129054120500203BIB008","volume-title":"An Introduction to Automata Theory and Formal Languages","author":"Linz P.","year":"2016"},{"key":"S0129054120500203BIB009","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-58-62"},{"issue":"3","key":"S0129054120500203BIB010","first-page":"267","volume":"21","author":"Mahalingam K.","year":"2018","journal-title":"Romanian J. Inform. Sci. Technol."},{"key":"S0129054120500203BIB011","series-title":"Graduate Texts in Mathematics","volume-title":"Model Theory: An Introduction","author":"Marker D.","year":"2002"},{"key":"S0129054120500203BIB012","volume-title":"A Course in Model Theory: An Introduction to Contemporary Mathematical Logic","author":"Poizat B.","year":"2012"},{"key":"S0129054120500203BIB013","first-page":"54:1","volume-title":"35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)","volume":"96","author":"Rajasekaran A.","year":"2018"},{"key":"S0129054120500203BIB015","volume-title":"Introduction to the Theory of Computation","author":"Sipser M.","year":"2006","edition":"2"},{"key":"S0129054120500203BIB016","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"2000","edition":"2"},{"key":"S0129054120500203BIB017","first-page":"467","volume":"57","author":"Vaught R.","year":"1954","journal-title":"Koninkl. Ned. Akad. Wettensch. Proc. Ser. A"},{"key":"S0129054120500203BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0090176"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120500203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T09:27:40Z","timestamp":1594286860000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120500203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":17,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["10.1142\/S0129054120500203"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120500203","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6]]}}}