{"entities":{"Q1819939":{"pageid":1830681,"ns":120,"title":"Item:Q1819939","lastrevid":69402387,"modified":"2026-04-13T06:45:51Z","type":"item","id":"Q1819939","labels":{"en":{"language":"en","value":"Boundedness, empty channel detection, and synchronization for communicating finite automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3995067"}},"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":"Q1819939$4C7BEF36-9094-4510-A28A-C334E71F99A6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a45c24db2a2b811e148b3b25ec59bf2f29969bc0","datavalue":{"value":{"text":"Boundedness, empty channel detection, and synchronization for communicating finite automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1819939$2D235BFD-74EC-4333-BB06-7B97BD31B1B4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ec24e03e081ef888bf4a0a8112c5c344ced1bb86","datavalue":{"value":"0614.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819939$0F4B3788-AFD4-4736-A190-0D82C272902A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3ad9a26720027dd13e72fa340be48a98734e84d6","datavalue":{"value":"10.1016/0304-3975(86)90110-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819939$1421C57E-C865-4ED6-A179-AFC8468A698D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b0fbe9a2f35bfbb97131fdd4f5f88a8af0c602f0","datavalue":{"value":{"entity-type":"item","numeric-id":688713,"id":"Q688713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$50F797DB-9312-4FE6-887E-6ACB8CB58D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef70989854b46304c6274e59f7064331acfcdafe","datavalue":{"value":{"entity-type":"item","numeric-id":344509,"id":"Q344509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$5904E330-AAD4-4D05-82B3-88A680DBE565","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":"Q1819939$181C0B54-240D-4B20-AF81-518B42ABB60D","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":"Q1819939$BCF14DCD-CA03-4DD9-AC96-7F4F3E183B49","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5b0c9a1da42b5a09e2fff5f2682651bcf0cc9145","datavalue":{"value":"Communicating finite automata are built out of a net of finite state machines (CFSM) each of which can make local moves, send/receive messages (to/from another component machine) and test the input/output channel on emptiness. The channels may be organized as FIFO queues (FIFO network of CFSM) or as multisets with priority (given by a partial order relation on the (finite) set of messages). A system of CFSM is said to be bounded iff there is a bound k such that in any reachable state of the system on any channel there are at most k messages. The main result of the paper is the decidability of the boundedness problem for a FIFO-system of two CFSM, where one of the two machines is allowed to send only a single type of message to the other. The authors give a nondeterministic logspace decision procedure using a simulation by a restricted 3-counter machine. This is in contrast to the undecidability of the boundedness problem for 2-dimensional vector addition systems with states (VASS) and similar systems of two CFSM with undecidable boundedness problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819939$7C36B21C-DE40-4D82-B504-6CCD9AAA3340","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819939$897D5D20-742F-436A-B138-5C0326517CE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819939$647709F1-0655-44AC-A9F6-89A6C9B732E4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"68e5d43c086425db25a5a206c64c738514ba2e02","datavalue":{"value":"3995067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819939$4D001E43-BA35-4641-983C-AF15546B7C97","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77f3393ee1bf5e04c83e196aa8891cae0cc3cb71","datavalue":{"value":"communicating finite state machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819939$E3F54C63-03B2-405D-A396-6732965FEC44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c64014e4863b2ca01e07e4e9adf65c2907c900d","datavalue":{"value":"FIFO queues","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819939$A13C202A-0144-4C84-9991-25C69F111D27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"429006b5baa467a8cd095b3e45d9142e29c2d61d","datavalue":{"value":"decidability of the boundedness problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819939$5AD04021-7273-4304-B1A9-8448ADA1F97E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb79299daf8f29391d6c8a2b4222865ffe474551","datavalue":{"value":"decision procedure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819939$9F170B86-1BE5-4911-9436-041062F2FFAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"810b7455d4a0c7cac919aba24740d34ffe513664","datavalue":{"value":"restricted 3-counter machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819939$6E032D94-977C-443E-8640-D5200D5B983F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01596681fec0062ebe65a0738936e768a85631a0","datavalue":{"value":"vector addition systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819939$214FF685-3FDC-42C8-AC76-9CAD9A9DC57B","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":"Q1819939$507903DD-ACE4-4559-8D8C-654C91EB0E48","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f96300a3eaf3dd19c688798f1cfcfee16088f095","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90110-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1819939$F708ACE3-8B29-4AFF-997B-6C13B7F94DFF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eafe17aab7a8419e5c115b915ccb114fa97a14d8","datavalue":{"value":"W2017140475","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819939$ACC75D17-B924-48CF-9D0B-C658F5AEA925","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a05f05f61b46a8fd8bda9fb47a75f81f498f2f8","datavalue":{"value":{"entity-type":"item","numeric-id":3657436,"id":"Q3657436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$BBAFAF62-90DB-46A9-802A-41AAD3514F59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9285a61f3039e7ce640456a9ea2b4d13665dc77","datavalue":{"value":{"entity-type":"item","numeric-id":5626625,"id":"Q5626625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$A690D780-A1FB-4B90-85CC-40FEC4C55216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f70028e31ae896a0df7dcbc67d83856a5a6ec6a","datavalue":{"value":{"entity-type":"item","numeric-id":3677157,"id":"Q3677157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$495A666D-C314-46B7-9801-43E113EB82C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08663cfc9ad28dad7443bdb814e24552eb8a9051","datavalue":{"value":{"entity-type":"item","numeric-id":1155361,"id":"Q1155361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$2DD91427-83B1-4E05-8406-9FA3FA3E51F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$87C72F75-EE03-4C46-8A9C-606A8A0DDDDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d396cb7909eb8ef7cf9892a2d4d1be562fcbdc7","datavalue":{"value":{"entity-type":"item","numeric-id":4109298,"id":"Q4109298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$8C5A87BF-D440-4D67-AF53-735352443BCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28a33b862f7d8441651d4cdc6c39e4250de110d1","datavalue":{"value":{"entity-type":"item","numeric-id":2540014,"id":"Q2540014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$14E56BD8-5257-406A-85BA-BA44A5F9EA07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed9702c45f558cf37c1cf27f32342d8410b993ac","datavalue":{"value":{"entity-type":"item","numeric-id":4157944,"id":"Q4157944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$BD87F085-6374-4672-AC1F-7EFE7B2B90EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4b1d274c6ee4b9c24930fb83b43c12797e99121","datavalue":{"value":{"entity-type":"item","numeric-id":5590814,"id":"Q5590814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$1E474799-4230-466A-95FA-D627ED594C81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40b5467bac8c2b14c65957d9305470ea5fcf1d67","datavalue":{"value":{"entity-type":"item","numeric-id":3911403,"id":"Q3911403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$17A58C2D-B957-4C13-A97B-357F864D1D6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"840c3498537d17d4f80bc9be5196dacc95600a62","datavalue":{"value":{"entity-type":"item","numeric-id":1242682,"id":"Q1242682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$9FBB73A9-1796-4ECA-AF0D-503EE2D443F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d41130d929b557eb6098b4637331c9cf6c8ff15","datavalue":{"value":{"entity-type":"item","numeric-id":1064050,"id":"Q1064050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$D320B430-BC6B-45C2-BEBA-2243738184F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$8ECDA66B-7CDE-4ADA-9F01-DAE6C987EEAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4f200ddc20c2d33390fb94670a066f08d95c0e9","datavalue":{"value":{"entity-type":"item","numeric-id":1215271,"id":"Q1215271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$F440AC0C-FCBB-412E-9311-7653BB5C8CB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"202fa537549d862287e8c72112377f480beedfed","datavalue":{"value":{"entity-type":"item","numeric-id":1218272,"id":"Q1218272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$E37768D3-34DF-46B9-868C-108A54BAAB4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"175f563c238c6df4ddc789404abf4b9fdce5a158","datavalue":{"value":{"entity-type":"item","numeric-id":1054479,"id":"Q1054479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819939$03DF3FE8-A6B3-44DE-A405-AFE2B0ADEF4C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"318be57b5465ad3075e379302d1bd7b0820a486b","datavalue":{"value":{"entity-type":"item","numeric-id":3685206,"id":"Q3685206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"448f572840d53ed38d86989ee7bbcf133fee949f","datavalue":{"value":{"amount":"+0.9271571040153505","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":"Q1819939$69D4DCFA-507D-4290-B57C-06681FAD976E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c963e23b50912df180fd46132ffafe96bd57fd9","datavalue":{"value":{"entity-type":"item","numeric-id":5431917,"id":"Q5431917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19c2785582fd63ac6fc79922eb4f4300c67f013e","datavalue":{"value":{"amount":"+0.8386114835739136","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":"Q1819939$36A3AB40-83FF-4E9A-A1DD-094B6C481B84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf7295fcd5233cfdcf83fc78f131cbe89109e0c2","datavalue":{"value":{"entity-type":"item","numeric-id":3216146,"id":"Q3216146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1bb82bff4fcafb0e42538ab6eef5568bba8c370","datavalue":{"value":{"amount":"+0.8209074139595032","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":"Q1819939$2C6E1A2D-9521-4C47-AEEC-94E768A90DDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4aeb892c23045d1f7d36b4bad8c60f0dadbe4936","datavalue":{"value":{"entity-type":"item","numeric-id":3677157,"id":"Q3677157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4bc6eef09257e3c38b08fe1055f8d2295263457","datavalue":{"value":{"amount":"+0.802988588809967","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":"Q1819939$60134019-E829-4524-9813-6E6C1D0005B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b4349491242e40d0f2631481009db3469a38b6d","datavalue":{"value":{"entity-type":"item","numeric-id":2735908,"id":"Q2735908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c44405dbce2baf11b1920f955157b45abc6f987a","datavalue":{"value":{"amount":"+0.7816078066825867","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":"Q1819939$396A42A4-D7C7-4731-858E-E36CE61F28C8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Boundedness, empty channel detection, and synchronization for communicating finite automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Boundedness,_empty_channel_detection,_and_synchronization_for_communicating_finite_automata"}}}}}