乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T09:42:14Z","timestamp":1661593334820},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T00:00:00Z","timestamp":1660262400000},"content-version":"vor","delay-in-days":11,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FE 560\/9-1"],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"Abstract<\/jats:title>Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property\u00a0

$$\\varPhi $$<\/jats:tex-math>\n \u03a6<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there is a graph satisfying\u00a0

$$\\varPhi $$<\/jats:tex-math>\n \u03a6<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in the family? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided by studying the syntactic monoid of the specification language\u00a0L<\/jats:italic> if a certain torsion condition is satisfied. This condition holds trivially if L<\/jats:italic> is regular. More specifically, we use a natural binary encoding of finite graphs over a binary alphabet

$$\\varSigma $$<\/jats:tex-math>\n \u03a3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and we define a regular set

$$\\mathbb {G}\\subseteq \\varSigma ^*$$<\/jats:tex-math>\n \n G<\/mml:mi>\n \u2286<\/mml:mo>\n \n \u03a3<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that every nonempty word

$$w\\in \\mathbb {G}$$<\/jats:tex-math>\n \n w<\/mml:mi>\n \u2208<\/mml:mo>\n G<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> defines a finite and nonempty graph. Also, graph properties can then be syntactically defined as languages over

$$\\varSigma $$<\/jats:tex-math>\n \u03a3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Then, we ask whether the automaton

$$\\mathcal {A}$$<\/jats:tex-math>\n A<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> specifies some graph satisfying a certain property\u00a0

$$\\varPhi $$<\/jats:tex-math>\n \u03a6<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our structural results show that we can answer this question for all \u201ctypical\u201d graph properties. In order to show our results, we split L<\/jats:italic> into a finite union of subsets and every subset of this union defines in a natural way a single finite graph F<\/jats:italic> where some edges and vertices are marked. The marked graph in turn defines an infinite graph\u00a0

$$F^\\infty $$<\/jats:tex-math>\n \n F<\/mml:mi>\n \u221e<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and therefore the family of finite subgraphs of

$$F^\\infty $$<\/jats:tex-math>\n \n F<\/mml:mi>\n \u221e<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> where F<\/jats:italic> appears as an induced subgraph. This yields a geometric description of all graphs specified by\u00a0L<\/jats:italic> based on splitting L<\/jats:italic> into finitely many pieces; then using the notion of graph retraction, we obtain an easily understandable description of the graphs in each piece.<\/jats:p>","DOI":"10.1007\/s00236-022-00427-z","type":"journal-article","created":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T07:03:03Z","timestamp":1660287783000},"page":"357-385","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Properties of graphs specified by a regular language"],"prefix":"10.1007","volume":"59","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-5994-3762","authenticated-orcid":false,"given":"Volker","family":"Diekert","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-4444-3220","authenticated-orcid":false,"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0003-3097-3906","authenticated-orcid":false,"given":"Petra","family":"Wolf","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,12]]},"reference":[{"key":"427_CR1","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1016\/j.ic.2008.06.007","volume":"207","author":"T Anderson","year":"2009","unstructured":"Anderson, T., Loftus, J., Rampersad, N., Santean, N., Shallit, J.: Detecting palindromes, patterns and borders in regular languages. Inf. Comput. 207, 1096\u20131118 (2009)","journal-title":"Inf. Comput."},{"key":"427_CR2","doi-asserted-by":"crossref","unstructured":"Anisimov, A.V.: Group languages. Kibernetika 4, 18\u201324 (1971). English translation in Cybernetics and Systems Analysis 4, 594\u2013601 (1973)","DOI":"10.1007\/BF01071030"},{"key":"427_CR3","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s11786-016-0257-1","volume":"10","author":"S Bera","year":"2016","unstructured":"Bera, S., Mahalingam, K.: Structural properties of word representable graphs. Math. Comput. Sci. 10, 209\u2013222 (2016)","journal-title":"Math. Comput. Sci."},{"key":"427_CR4","volume-title":"Nonserial Dynamic Programming, vol.\u00a091 of Mathematics in Science and Engineering","author":"U Bertel\u00e8","year":"1972","unstructured":"Bertel\u00e8, U., Brioschi, F.: Nonserial Dynamic Programming, vol.\u00a091 of Mathematics in Science and Engineering. Academic Press, New York and London (1972)"},{"key":"427_CR5","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in Monadic Second-Order Logic. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformations, vol.\u00a01: Foundations, pp. 313\u2013400. World Scientific (1997)","DOI":"10.1142\/9789812384720_0005"},{"key":"427_CR6","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, vol. 138 of Encyclopedia of Mathematics and its Applications. Cambridge University Press (2012)","DOI":"10.1017\/CBO9780511977619"},{"key":"427_CR7","doi-asserted-by":"crossref","unstructured":"de\u00a0Melo, A.A., de\u00a0Oliveira\u00a0Oliveira, M.: Second-order finite automata. In: Fernau, H. (ed.) Computer Science: Theory and Applications\u201415th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29\u2013July 3, 2020, Proceedings, volume 12159 of Lecture Notes in Computer Science, pp. 46\u201363. Springer (2020)","DOI":"10.1007\/978-3-030-50026-9_4"},{"key":"427_CR8","doi-asserted-by":"crossref","unstructured":"Diekert, V., Fernau, H., Wolf, P.: Properties of graphs specified by a regular language. In: Moreira, N., Reis, R. (ed.) Developments in Language Theory\u201425th International Conference, DLT 2021, Porto, Portugal, August 16\u201320, 2021, Proceedings, vol. 12811 of Lecture Notes in Computer Science, pp. 117\u2013129. Springer (2021)","DOI":"10.1007\/978-3-030-81508-0_10"},{"key":"427_CR9","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, vol. 173 of Graduate Texts in Mathematics, 4th edn. Springer (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"427_CR10","volume-title":"Automata, Languages, and Machines","author":"S Eilenberg","year":"1974","unstructured":"Eilenberg, S.: Automata, Languages, and Machines, vol. A. Academic Press, New York and London (1974)"},{"key":"427_CR11","doi-asserted-by":"publisher","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg, S., Spanier, E.H.: Semigroups, Presburger formulas and languages. Pacific J. Math. 16, 285\u2013296 (1966)","journal-title":"Pacific J. Math."},{"key":"427_CR12","doi-asserted-by":"crossref","unstructured":"G\u00fcler, D., Krebs, A., Lange, K., Wolf, P.: Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy. In: Klein, S.T., Mart\u00edn-Vide, C., Shapira, D. (eds.) Language and Automata Theory and Applications\u201412th International Conference, LATA 2018, Ramat Gan, Israel, April 9\u201311, 2018, Proceedings, vol. 10792 of Lecture Notes in Computer Science, pp. 156\u2013168. Springer (2018)","DOI":"10.1007\/978-3-319-77313-1_12"},{"key":"427_CR13","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01917434","volume":"8","author":"R Halin","year":"1976","unstructured":"Halin, R.: $$s$$-functions for graphs. J. Geom. 8, 171\u2013186 (1976)","journal-title":"J. Geom."},{"key":"427_CR14","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1006\/jabr.1995.1105","volume":"173","author":"O Kharlampovich","year":"1995","unstructured":"Kharlampovich, O.: The word problem for the Burnside varieties. J. Algebra 173, 613\u2013621 (1995)","journal-title":"J. Algebra"},{"key":"427_CR15","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s11083-008-9083-7","volume":"25","author":"S Kitaev","year":"2008","unstructured":"Kitaev, S., Seif, S.: Word problem of the Perkins semigroup via directed acyclic graphs. Order 25, 177\u2013194 (2008)","journal-title":"Order"},{"key":"427_CR16","first-page":"157","volume":"48","author":"P Kristiansen","year":"2004","unstructured":"Kristiansen, P., Hedetniemi, S.M., Hedetniemi, S.T.: Alliances in graphs. J. Comb. Math. Comb. Comput. 48, 157\u2013177 (2004)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"427_CR17","doi-asserted-by":"crossref","unstructured":"Kuske, D.: Second-order finite automata: expressive power and simple proofs using automatic structures. In: Moreira, N., Reis, R. (eds.) Developments in Language Theory\u201425th International Conference, DLT 2021, Porto, Portugal, August 16\u201320, 2021, Proceedings, vol. 12811 of Lecture Notes in Computer Science, pp. 242\u2013254. Springer (2021)","DOI":"10.1007\/978-3-030-81508-0_20"},{"key":"427_CR18","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1109\/5.892708","volume":"88","author":"NJ Larsson","year":"2000","unstructured":"Larsson, N.J., Moffat, A.: Off-line dictionary-based compression. Proc. IEEE 88, 1722\u20131732 (2000)","journal-title":"Proc. IEEE"},{"key":"427_CR19","doi-asserted-by":"publisher","first-page":"1150","DOI":"10.1016\/j.is.2013.06.006","volume":"38","author":"M Lohrey","year":"2013","unstructured":"Lohrey, M., Maneth, S., Mennicke, R.: XML tree structure compression using RePair. Inf. Syst. 38, 1150\u20131167 (2013)","journal-title":"Inf. Syst."},{"key":"427_CR20","volume-title":"Papert, Seymour: Counter-Free Automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R.: Papert, Seymour: Counter-Free Automata. The MIT Press, Cambridge, Mass (1971)"},{"key":"427_CR21","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(83)90003-X","volume":"26","author":"DE Muller","year":"1983","unstructured":"Muller, D.E., Schupp, P.E.: Groups, the theory of ends, and context-free languages. J. Comput. Syst. Sci. 26, 295\u2013310 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"427_CR22","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"RJ Parikh","year":"1966","unstructured":"Parikh, R.J.: On context-free languages. J. ACM 13, 570\u2013581 (1966)","journal-title":"J. ACM"},{"key":"427_CR23","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.: Graph minors. III. Planar tree-width. J. Comb. Theory 36, 49\u201364 (1984)","journal-title":"J. Comb. Theory"},{"key":"427_CR24","doi-asserted-by":"crossref","unstructured":"Rubtsov, A.A., Vyalyi, M.N.: Automata equipped with auxiliary data structures and regular realizability problems. In: Han, Y-S., Ko, S-K. (eds.) Descriptional Complexity of Formal Systems\u201423rd IFIP WG 1.02, International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings, vol. 13037 of Lecture Notes in Computer Science, pp. 150\u2013162. Springer (2021)","DOI":"10.1007\/978-3-030-93489-7_13"},{"key":"427_CR25","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"MP Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.P.: On finite monoids having only trivial subgroups. Inf. Control 8, 190\u2013194 (1965)","journal-title":"Inf. Control"},{"key":"427_CR26","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0168-0072(91)90054-P","volume":"53","author":"D Seese","year":"1991","unstructured":"Seese, D.: The structure of the models of decidable monadic theories of graphs. Ann. Pure Appl. Logic 53, 169\u2013195 (1991)","journal-title":"Ann. Pure Appl. Logic"},{"key":"427_CR27","unstructured":"Trahtenbrot, B.A.: The impossibility of an algorithm for the decision problem for finite domains (in Russian). Doklady Akademii Nauk SSSR, New Series 70, 569\u2013572 (1950). English Translation in American Mathematical Society, Translations 23, 1\u20135 (1963)"},{"key":"427_CR28","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1134\/S0032946015040043","volume":"51","author":"MN Vyalyi","year":"2015","unstructured":"Vyalyi, M.N., Rubtsov, A.A.: On regular realizability problems for context-free languages. Probl. Inf. Transm. 51, 349\u2013360 (2015)","journal-title":"Probl. Inf. Transm."},{"key":"427_CR29","unstructured":"Wolf, P.: Decidability of the Regular Intersection Emptiness Problem. Master\u2019s thesis, Universit\u00e4t T\u00fcbingen, Germany (2018)"},{"key":"427_CR30","doi-asserted-by":"crossref","unstructured":"Wolf, P.: On the decidability of finding a positive ILP-instance in a regular set of ILP-instances. In: Hospod\u00e1r, M., Jir\u00e1skov\u00e1, G., Konstantinidis, S. (eds.) Descriptional Complexity of Formal Systems\u201421st IFIP WG 1.02 International Conference, DCFS 2019, Ko\u0161ice, Slovakia, July 17\u201319, 2019, Proceedings, vol. 11612 of Lecture Notes in Computer Science, pp. 272\u2013284. Springer (2019)","DOI":"10.1007\/978-3-030-23247-4_21"},{"key":"427_CR31","unstructured":"Wolf, P.: From decidability to undecidability by considering regular sets of instances. In: Cordasco, G., Gargano, L., Rescigno, A.A. (eds.) Proceedings of the 21st Italian Conference on Theoretical Computer Science, Ischia, Italy, September 14\u201316, 2020, vol. 2756 of CEUR Workshop Proceedings, pp. 33\u201346. CEUR-WS.org (2020)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00427-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-022-00427-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00427-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T09:09:29Z","timestamp":1661591369000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-022-00427-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["427"],"URL":"https:\/\/doi.org\/10.1007\/s00236-022-00427-z","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8]]},"assertion":[{"value":"12 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}