{"entities":{"Q1084096":{"pageid":1094848,"ns":120,"title":"Item:Q1084096","lastrevid":66698433,"modified":"2026-04-12T12:11:34Z","type":"item","id":"Q1084096","labels":{"en":{"language":"en","value":"The theory of ends, pushdown automata, and second-order logic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3976992"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$EFF074B6-8BFB-4F3C-A7F3-A8248403CB7D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"be95d79b864c0cfa348c81d7391543b2bcefb9e6","datavalue":{"value":{"text":"The theory of ends, pushdown automata, and second-order logic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1084096$CC348AE1-7768-4DCB-AB39-CEE2B447962F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6f8a466db212d45a830f63a66ccf85d3c875b24a","datavalue":{"value":"0605.03005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084096$886CBEFC-B96E-485B-8FDD-E24580E0E00A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c9581bb8258cf2bb734c8bd65f0cf0e5ae06ba02","datavalue":{"value":"10.1016/0304-3975(85)90087-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084096$E9CD6D8E-23BA-4BBB-9F46-EAB418F6D700","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"21d8423f1327302bd91c424093d3752a15cfe97d","datavalue":{"value":{"entity-type":"item","numeric-id":673777,"id":"Q673777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$7A37F926-4086-4DAB-97FB-BC16EF7F2E4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"698bc4fe65f79b85d517df655a1aca4a01c66cfe","datavalue":{"value":{"entity-type":"item","numeric-id":444387,"id":"Q444387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$4C9BDF6F-FE11-46A2-90ED-87E4DA084A32","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$619A0334-C200-43E9-96B1-A99B6611AA0B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1084096$72FFE0B1-ABC8-468E-9DC7-2DCCBCBA4B74","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4fed9638dd7dcacbe001fcc8b9ef8f600ffc1354","datavalue":{"value":"In this carefully written paper the authors give detailed graph-theoretic proofs of several interesting finiteness results in the automata theory of ends, which deals with well behaved ways of going to infinity. Their approach is to define a broad class of graphs called ''context-free graphs''. Basically, the underlying idea is that a context-free graph is well behaved at infinity. The bottom line is that a graph is context-free iff it is the complete transition graph of some pushdown automaton.    Such graphs are generalizations of Cayley graphs of context-free groups. Using Rabin's theorem on the decidability of monadic second-order theory for the infinite binary tree, such graphs have also a decidable monadic second-order theory. Solvable decision problems about tiling systems and cellular automata are discussed in great detail.    Finally, the authors show that the membership problem and the inclusion problem for reachability sets of vector addition systems on a context- free graph are uniformly solvable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$C7BCF6C9-F9AC-45C2-B67A-76DDD024A848","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084096$46ED9648-6BC5-49F1-BBE4-60EFE10F305F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084096$05BCFF7E-A54B-42E8-84D7-6B4B58FF5EFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084096$3A09C761-B866-4768-9E28-9BAFE021FC3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4920bcb5055cf3da94830f00d832c01308357d4b","datavalue":{"value":"05B45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084096$CDC988FC-9A71-4658-8C39-6F11011803BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084096$27C06EE3-150C-4B18-9A50-59026F7CAAA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084096$3587EEB8-DE8F-4FF8-8FE1-AB2221409AA6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"18832e17a1e43f55b50bcdb8d6376a04dfc07b47","datavalue":{"value":"3976992","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084096$7F988259-4328-4E06-9D45-5BFC9A9D5098","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"456c672ca15cab74651e643baa7549046be81ae8","datavalue":{"value":"pushdown automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$8001387F-6849-4E21-97C4-8EB4E36267AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed96de97b0a609b359b7c86a233bcbfc19923f4a","datavalue":{"value":"finiteness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$1EE687B2-AE55-469C-B8E4-C965BAEE02D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4511c7aef5d777bdd1eca2b2842ee3ce5a571c09","datavalue":{"value":"automata theory of ends","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$CA70A2EB-D08C-488F-8792-3767B4F2BA81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"351b7770fc63c9957adb4113bc7d1e61db4fa221","datavalue":{"value":"infinity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$D7B8191F-DC28-4285-96C9-40A14DF2F277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b58a9db06da05029b9b9e50c5b23ff5479c4757","datavalue":{"value":"context-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$5CF48C06-30CA-48BA-B23A-0B65729E8AE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0488673ac4d7f483985d2cc228ccdf424b87cf5","datavalue":{"value":"transition graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$30B4657B-3B10-4014-AC87-1AC1CF493E38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc12dc8c7c76c2a2052bfc1a919f057f128c1835","datavalue":{"value":"Cayley graphs of context-free groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$87C92D8B-FBFA-4D6C-BA1F-DE3BB740B494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60cf33f7d54987daf9d4ce122dd8c17f56f9b0ab","datavalue":{"value":"decidable monadic second-order theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$3E58B96B-AD3D-4F8A-B409-A324BF87FC44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27638d630e18a79d37aae3ab247a2d08a15508a4","datavalue":{"value":"decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$6FE35955-99D6-4B01-8D29-263BF4E56375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddef4950009ab088741f3b2a52195162bd4e4298","datavalue":{"value":"tiling systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$93005F44-D779-49C0-8BE5-B257F40E1BAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc4b5d63289db850b148e760ad6fea530c4e5631","datavalue":{"value":"cellular automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$08365979-D7D4-4955-B840-12364F0D3A09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a2a5aaf2813613e191091bab6a7937bd2f6db3d","datavalue":{"value":"membership problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$EC450505-0566-4FB9-992C-CB8BC4AC4BBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7114076c4de8260aebdf2057b14978825a8e3d2e","datavalue":{"value":"inclusion problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$06384AD4-C65F-4C3B-8EAE-98BDBA2537BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b51e85345aea1edf04e319669d190f63a8e78b3d","datavalue":{"value":"reachability sets of vector addition systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084096$68A520AD-DF05-4E5C-BC63-7EE7E726B32E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ba7232f3f7ae68133198ecf25821b70a187e9eaa","datavalue":{"value":{"entity-type":"item","numeric-id":704043,"id":"Q704043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$F42AD9BC-38E8-4FD6-B1B6-30ED6CEF0A42","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$5A7F46E2-A943-4507-BF1E-C7BA2484566C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e7703edc634786f8ebbcf14a7c45b26958ed527a","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90087-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1084096$7030501F-553D-4600-9890-40E164224BB0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8298b76db07b7c13c602c10f3d95ff892295b2e7","datavalue":{"value":"W1971416129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084096$6C62674C-7786-4BA1-87AC-8DB212548203","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"248a2d26a1ca08934deac5e7bece6864db39e79f","datavalue":{"value":{"entity-type":"item","numeric-id":5921451,"id":"Q5921451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$2988347B-FF29-4D9B-92CE-9608BF75732D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f84c82de96fb7c7b710e84da042fa6d2d7d4ea68","datavalue":{"value":{"entity-type":"item","numeric-id":5520636,"id":"Q5520636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$C980EA79-2F80-474B-B67B-1B436D9DB9F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6981775c3bdaad566fe065afd3c04ece6176878a","datavalue":{"value":{"entity-type":"item","numeric-id":1238997,"id":"Q1238997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$A5AC7D05-E9EB-46B6-AEC6-51D0E9BCE8E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$CDE7A2F7-8E64-403B-AA0C-52EBD768EEB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$41E1CE41-1444-4C92-B166-6DA1E97A8D95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2af188522ee36dfbc40e8063345c06265fc901ae","datavalue":{"value":{"entity-type":"item","numeric-id":792454,"id":"Q792454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$F85AE822-33C7-4142-8FC4-F400B75EC2AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b476279f9ef74fddb27272ad70ec34f0a4ec2a74","datavalue":{"value":{"entity-type":"item","numeric-id":5625141,"id":"Q5625141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$6FD15DBC-BD75-4CE4-89F9-E7F1FDB5FDCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4a83a1ca4d4fde49a64a4b02cfd93f8a6844ca3","datavalue":{"value":{"entity-type":"item","numeric-id":5651924,"id":"Q5651924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084096$E0EBE5A0-1B4B-4258-A3FF-7D5C6B9DCF71","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0a6750aaf9fedc5ba3940f138ad04d2146777a7","datavalue":{"value":{"entity-type":"item","numeric-id":3785987,"id":"Q3785987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a59a48eac2abccb776af0dbf4a6ba87a1f52473","datavalue":{"value":{"amount":"+0.7970920205116272","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1084096$56705FD8-39D1-4F03-A5CB-FF06A76DFA55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf19450b8e83b3e484f008b77185c796427475c3","datavalue":{"value":{"entity-type":"item","numeric-id":4818835,"id":"Q4818835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08236bd6bec2131fc09ef24aaa4dd61cdf1e7c98","datavalue":{"value":{"amount":"+0.7945528030395508","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1084096$7995031F-4207-4AFA-B8C7-9893275BC88A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99d4fc9884a5b4e02dcaa1c526d72d1be060f6ea","datavalue":{"value":{"entity-type":"item","numeric-id":1853615,"id":"Q1853615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"314f2395dc1d73dfa93d1bfb83badc186bfa8695","datavalue":{"value":{"amount":"+0.79096919298172","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1084096$AFACD6F5-7A1D-4C1D-8283-75D0B6CF7EBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8008e45298675cd047c5fdfbc895205a7c8ef914","datavalue":{"value":{"entity-type":"item","numeric-id":444388,"id":"Q444388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0feeecdbbabd3f4a0bd8684425cf17f60087d729","datavalue":{"value":{"amount":"+0.7861272692680359","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1084096$9B7266BC-E09C-48E5-8307-4607B79A0817","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db0d2181a2077520f6bf2e1ffdda5724586c2c25","datavalue":{"value":{"entity-type":"item","numeric-id":1877692,"id":"Q1877692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46061d2ed58b3cbdc0d42576d2f1561ede2c0077","datavalue":{"value":{"amount":"+0.7792679071426392","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1084096$82C1449B-97C6-49ED-9914-3B3DCC0F5FA7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The theory of ends, pushdown automata, and second-order logic","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_theory_of_ends,_pushdown_automata,_and_second-order_logic"}}}}}