{"entities":{"Q1079372":{"pageid":1090124,"ns":120,"title":"Item:Q1079372","lastrevid":66093222,"modified":"2026-04-12T07:30:11Z","type":"item","id":"Q1079372","labels":{"en":{"language":"en","value":"A property of real-time trellis automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3963204"}},"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":"Q1079372$B1F69602-21C2-4945-8960-1A8A6A4DCAE5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"55cef7f10ba857580776b0c2e5ddf5fba6b00fd8","datavalue":{"value":{"text":"A property of real-time trellis automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1079372$D2F72437-39CE-4E85-80B6-0410CC045CBA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b982051ab28638086ec83592988e55db32596f1d","datavalue":{"value":"0597.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079372$8452E36C-C2E1-439B-B9A5-B429BD23E3AE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8c5de82a3d67e1149fd39918bb8ed837f425bc4d","datavalue":{"value":"10.1016/0166-218X(86)90025-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079372$0CA47033-D821-4FB3-A453-DD4A1827A394","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079372$D5C4F8EA-34D9-40C9-BB0B-8EF676E49F92","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1079372$7108D9ED-6329-4C07-A5BA-3F94E2388BC8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cfc339f35cde3c527b7cf55aa7910b4a47c99754","datavalue":{"value":"If L is a language acceptable by a real-time trellis automaton having N states [for the definition see for instance \\textit{K. Culik II}, \\textit{J. Gruska} and \\textit{A. Salomaa}, Int. J. Comput. Math. 15, 195-212 (1984; Zbl 0571.68041)] and there exist words x, w such that \\(xw^*\\cap L\\) is infinite then there exists a natural k and a natural \\(K\\leq N^{| x| +1}\\) such that for all \\(n\\geq 0\\) the words \\(xw^{k+nK}\\) belong to L.    Making use of this property one can sometimes easily show that a given language is no real-time trellis language. The author illustrates this for \\(L_ 1=\\{a^ nb^{mn}:\\) \\(n,m>0\\}\\), \\(L_ 2=\\{a^{2^ n}:\\) \\(n\\geq 0\\}\\), and \\(L_ 3=\\{a^ p:\\) p is a prime\\(\\}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079372$E07AF223-58B5-4C2E-9530-A1FFFD8B392F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079372$E14FD2F5-F588-4119-B3CD-261CAA1F9C60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079372$9EC2B727-A4D7-4E72-86A4-EAB8440C7208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079372$590D0F67-EF65-4FCD-B9E9-33A024B607E6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2664d8196c06ce790abecc71ea014b24c04a64f4","datavalue":{"value":"3963204","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079372$E6A8DB97-EFBF-4F6B-8FAE-565643D7C8DA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77094d165b20aa4e5bc9030dde56ea585ae9a33b","datavalue":{"value":"real-time acceptance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079372$A6290C05-EF9A-4E76-96F3-B04F5A509723","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f143d75162aea6d3b09de1ba925afc74ef470da4","datavalue":{"value":{"entity-type":"item","numeric-id":418765,"id":"Q418765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079372$DE82425B-87C7-49E3-AFDF-30A136FF37C8","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":"Q1079372$0E3ABA42-2C34-4E7C-BEFA-F87699E1DC0D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b19686091b84a7150d67d37efa1f8c458c00474f","datavalue":{"value":{"entity-type":"item","numeric-id":790615,"id":"Q790615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079372$7CA87120-C5B5-4A5B-9DB5-9EF48DDBFC42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4adc507e192ae0675e164c7bd30682da834f3c9","datavalue":{"value":{"entity-type":"item","numeric-id":3687722,"id":"Q3687722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079372$9F0FC2CA-6483-4B9B-878D-B0E3EB30CDF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be8001a5615e3f4fe974a4d5d59e09f623287067","datavalue":{"value":{"entity-type":"item","numeric-id":3687723,"id":"Q3687723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079372$BE648737-5CCD-4A6C-9D93-4E7B170F4F23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34d399c657348baa004087caf4bfb28e90f3df58","datavalue":{"value":{"entity-type":"item","numeric-id":792091,"id":"Q792091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079372$4ABE3845-7503-4548-9986-76EE36E8837C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cc4af2c13b62023765ebcc8d1bc83684b697f7bd","datavalue":{"value":"https://doi.org/10.1016/0166-218x(86)90025-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1079372$92192188-91C3-417D-A35C-A142E4D237DD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"22931ba0448022a7c593c57ef8e9297ff21d4f75","datavalue":{"value":"W2019846069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079372$18C62D96-C61B-4155-B44A-231D6C2D0935","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d68110ee12e726b9d1d56653dd4db46f073967f","datavalue":{"value":{"entity-type":"item","numeric-id":3783573,"id":"Q3783573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d725e917f9acd616f5d4b3d0402bd369c0b291b8","datavalue":{"value":{"amount":"+0.7695609331130981","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":"Q1079372$0E38F595-4156-4347-9A87-3D580A0D0E63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94c96ba92e16a8b2f4c0f2933bdfa1743cd193c6","datavalue":{"value":{"entity-type":"item","numeric-id":3974870,"id":"Q3974870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a271e73535384aacc1ba7acede29f0fa35b1eb12","datavalue":{"value":{"amount":"+0.7667045593261719","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":"Q1079372$BE2A3170-0B39-48CB-B44F-078B0880F4DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b9f13cba21f259673f7005e35c998233877b4b5","datavalue":{"value":{"entity-type":"item","numeric-id":4837658,"id":"Q4837658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b4c27cd11d368bad1ac3d9896cf799aab40e2e7","datavalue":{"value":{"amount":"+0.7609338164329529","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":"Q1079372$2731D4B9-D286-4DE6-B1BC-332BCAC1FC0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7905f401487041fc9d74e4666ff6de1507aad201","datavalue":{"value":{"entity-type":"item","numeric-id":1704113,"id":"Q1704113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a886ac0f3a001815742a48c9d9818e3138bd7662","datavalue":{"value":{"amount":"+0.753695011138916","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":"Q1079372$AFF9AE71-082F-41F9-B28E-9D275B889AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"614031b66fc02512b7bfff3250d984f078e6554c","datavalue":{"value":{"entity-type":"item","numeric-id":3030260,"id":"Q3030260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02f7d106130ae7dd4d092cb35e3c6044ac5c9c30","datavalue":{"value":{"amount":"+0.7454696297645569","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":"Q1079372$DE03BCCC-1719-4092-BB6F-EB25E6945A97","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A property of real-time trellis automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_property_of_real-time_trellis_automata"}}}}}