{"entities":{"Q685354":{"pageid":687203,"ns":120,"title":"Item:Q685354","lastrevid":63459501,"modified":"2026-04-11T13:18:13Z","type":"item","id":"Q685354","labels":{"en":{"language":"en","value":"On the regular structure of prefix rewriting"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417316"}},"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":"Q685354$8F3CE06E-462F-4565-ABAC-3969469F7BAD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"94525142f37340ff7c7715fb242b7c723394451e","datavalue":{"value":{"text":"On the regular structure of prefix rewriting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685354$ACACD153-5371-4DAF-9594-4095CEB3E3ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3d65fbd392b00f7b7e6ed9c9c4084c70e4372c69","datavalue":{"value":"0780.68077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685354$C6ED942D-ACE1-4E4B-97CD-35932C08115E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0c4a694d150fe54ede819105d331d9c18d945465","datavalue":{"value":"10.1016/0304-3975(92)90278-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685354$FCFFC889-53CA-45F8-B4B7-732B3AD9E654","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"80bd59cd009842eaf1c170b649eeda5dece3b2d9","datavalue":{"value":{"entity-type":"item","numeric-id":685353,"id":"Q685353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$20468EAD-BB91-4296-A9CA-1D8A6E637468","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":"Q685354$88EAB65B-7B26-47DE-B68B-0D83FD01B17F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d14a1cb4ea938484f5d10f46c92fb9051ec58aaa","datavalue":{"value":{"time":"+1994-02-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685354$1E75201B-ED2B-49F2-951C-D3FE286FD524","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8b8e08d277c622bc9adda7d4cdf0f2bbf50f449d","datavalue":{"value":"A labelled word rewriting system \\(R\\) on an alphabet \\(X\\) and a set \\(L\\) of labels is a finite set of labelled transitions \\(u@>a>>v\\) where \\(a\\) is a label and \\(u\\) and \\(v\\) are words over \\(X\\). The prefix transition graph of \\(R\\) is the infinite set of labelled transitions \\(uw@>a>>vw\\) where \\(u@>a>>v\\) is a rule of \\(R\\) and \\(w\\) is a word over \\(X\\).   We show that any prefix transition graph is effectively a regular graph of finite degree: it is produced from a finite graph by iterating the addition of a finite family of finite graphs. It turns out that the rational restrictions of the prefix transition graphs are exactly the regular graphs of finite degree. Furthermore we show that the prefix transition graphs and the regular graphs of finite degree have the same connected components and the same accessible subgraphs. Finally we establish that the prefix transition graphs corresponds to the transition graphs of pushdown automata. All constructions are effective.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685354$6FDC6C4E-4E1C-46D8-8016-099EC8722D50","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685354$B4569183-1FB9-4212-8669-2D1F2A9C059E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685354$0B6AC116-EF22-4609-AD6F-363E24BA1772","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cd5826993bfd9fcee31ccb05c78e6d201e3d5238","datavalue":{"value":"417316","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685354$C8521522-E98D-41D9-BCB2-C6EE305F74EA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4bfd5b0e8cb9c6ba00aff10d586e1836ddee85f1","datavalue":{"value":"labelled word rewriting system","type":"string"},"datatype":"string"},"type":"statement","id":"Q685354$D438AB55-BBF4-4F8C-BBCD-C8D9F64C582B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbb0fbc93b9644902d30ccdcbb91c6f28066fd06","datavalue":{"value":"prefix transition graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q685354$C42E626F-468C-4373-9A05-C2A3F3FDA25C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9217cf5fdf9311e03b0d651a5eac92fd9c7100c2","datavalue":{"value":"regular graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q685354$729BE40E-C719-4B2B-97F4-C879E27ECAE0","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":"Q685354$4B6289AF-F392-4B68-8890-224DA71AA531","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e95dab920df6bb4688d107a498b005a8577eead2","datavalue":{"value":{"entity-type":"item","numeric-id":3774929,"id":"Q3774929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$14588D0E-C0DA-4376-8769-F277FF772C8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08341059441af41c6921638de5b990f0ab22c6e3","datavalue":{"value":{"entity-type":"item","numeric-id":3907107,"id":"Q3907107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$D3BAA57B-A7ED-45D5-85D5-DA138E245707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e6473c3e86b72de5065fa5f2153919d4fac2fc8","datavalue":{"value":{"entity-type":"item","numeric-id":5338328,"id":"Q5338328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$D3C8DEE8-2119-4509-8B0E-1022E7E96216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83b1a50c5e6446a4595b4c668f78c20866c1b879","datavalue":{"value":{"entity-type":"item","numeric-id":4028125,"id":"Q4028125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$B071BED1-62A0-446B-A298-847589CD028C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b0c517836cf032c1bf576504acdb0ab7ca579ec","datavalue":{"value":{"entity-type":"item","numeric-id":3470112,"id":"Q3470112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$2D3C22B6-368A-46FF-B093-8DA89584205F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04613e27d09f9e082e14779fbb81073cab13e44a","datavalue":{"value":{"entity-type":"item","numeric-id":4205068,"id":"Q4205068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$EA79A9B0-69C8-4ED2-9313-B5578C3C701C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fce6b15d7f7c38b132fff8d032bbd1c4bb01ae91","datavalue":{"value":{"entity-type":"item","numeric-id":4035657,"id":"Q4035657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$37BA8BF8-1CCC-4567-ACCC-4D7D6E44881A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14f9918dd24d68d6a8b0715c23196dc11eb6c8fa","datavalue":{"value":{"entity-type":"item","numeric-id":684560,"id":"Q684560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$B1234942-4785-44AE-AD8D-02669008A4D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7baf863b093fb4d1a719d104d04793c3994ef02","datavalue":{"value":{"entity-type":"item","numeric-id":3774975,"id":"Q3774975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$9B53A416-FD91-40A9-89AF-49F6772D0652","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cd06688d0a2118d72cedd0d86de5ca69bef5bfd","datavalue":{"value":{"entity-type":"item","numeric-id":1084096,"id":"Q1084096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$015199A1-C85F-4D28-BEEB-7C9D20506B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0618da01793dd308fe44f4a7cd7a6f8b70dd5e31","datavalue":{"value":{"entity-type":"item","numeric-id":4385529,"id":"Q4385529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685354$145780CA-684C-423C-B8BC-07DC4B60ED8E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca7ccaa1ed133504d3de42fc29a5c13345fb5c7e","datavalue":{"value":{"entity-type":"item","numeric-id":4027621,"id":"Q4027621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e3fec66bc8a4a09910aa23396be148789a1dd29","datavalue":{"value":{"amount":"+0.8940509557723999","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":"Q685354$51A0AB28-1E84-4133-9E36-77DC4F0E4DC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"441508b9e262639b72720e32d6c510d10c87f17a","datavalue":{"value":{"entity-type":"item","numeric-id":3167007,"id":"Q3167007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e3fec66bc8a4a09910aa23396be148789a1dd29","datavalue":{"value":{"amount":"+0.8940509557723999","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":"Q685354$4A511B43-CEC9-4F36-9AB1-DB99FB625DAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3c331bab0771027ef135d4dd1d9fed2cb54b04d","datavalue":{"value":{"entity-type":"item","numeric-id":3525557,"id":"Q3525557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08f955537fd7ef9dea655e842e97ec99fa1b4f4f","datavalue":{"value":{"amount":"+0.7918134331703186","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":"Q685354$8D1B6C0A-8DF2-48DC-B22E-7813A7780E88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"faf8f4d06fa7449bff10565eae2d94565b6bd5dc","datavalue":{"value":{"entity-type":"item","numeric-id":4508292,"id":"Q4508292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c584d3f779d2285a0bc677b60fee7f6651a21fc9","datavalue":{"value":{"amount":"+0.7866368889808655","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":"Q685354$9CB850F8-B991-47F6-888A-8F3521A4F58A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e51313ed8d9ca762f90ec7167ed8610bc13aca48","datavalue":{"value":{"entity-type":"item","numeric-id":2330116,"id":"Q2330116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c584d3f779d2285a0bc677b60fee7f6651a21fc9","datavalue":{"value":{"amount":"+0.7866368889808655","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":"Q685354$827E8E1D-15D9-4040-9C8F-57E70DC9B844","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the regular structure of prefix rewriting","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_regular_structure_of_prefix_rewriting"}}}}}