{"entities":{"Q1191027":{"pageid":1201776,"ns":120,"title":"Item:Q1191027","lastrevid":69857271,"modified":"2026-04-13T10:48:49Z","type":"item","id":"Q1191027","labels":{"en":{"language":"en","value":"Regular languages in \\(NC\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 58912"}},"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":"Q1191027$1CBC965E-6BF3-40B7-9CEA-CC842EAEFAEC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ed68995593a7c8264c55c16e04f059beb9ac1b65","datavalue":{"value":{"text":"Regular languages in \\(NC\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1191027$A52D73DD-CC0A-4B96-B77D-F81F1B0ACC51","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"52087ed6649244102b74dd0b8e5a2b1143d2db8d","datavalue":{"value":"0757.68057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1191027$16E061C3-DD54-4F89-A55C-1426A2A10A4A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5583defa5db28848d6da99ba4dd8ddac808ffcd7","datavalue":{"value":"10.1016/0022-0000(92)90014-A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1191027$4C479B07-FA42-4716-9A1F-244D41A737D5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"795e5af62cffee265773a4ab5f77af480f86d75e","datavalue":{"value":{"entity-type":"item","numeric-id":386052,"id":"Q386052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$5666C78B-1B0E-4AF8-B633-CAB3DC9C8071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9fb8d4872513e25b3cb2ee4b054caa1dd9caebba","datavalue":{"value":{"entity-type":"item","numeric-id":599181,"id":"Q599181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$C5E2F4DB-0BDA-4AED-8AC6-09999CB064FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"46e384ba9e92c2d1801e5e36038afcb91974b185","datavalue":{"value":{"entity-type":"item","numeric-id":917542,"id":"Q917542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$93508ACA-B6F2-4AC8-AF26-50FDD8E33C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5fda2b843008097467141f2c2de99a1b410da08e","datavalue":{"value":{"entity-type":"item","numeric-id":685707,"id":"Q685707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$26A2DBB5-A510-47BD-8F46-DA5812A6A4A6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$4C715EB2-BCB5-47B2-88B1-CBC8FEC4C77C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1191027$1F41BF84-3E6F-4A14-ACCC-6066EFB43521","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9960ad71061f36e985b2d95f3a62a3c69f89b0b6","datavalue":{"value":"The paper deals with the problem of recognition of regular languages by the circuits of certain type. The theory of the syntactic monoid of a regular language is used to present various characterizations of the regular languages in the circuit complexity class \\(AC^ 0\\). Also an effective procedure for deciding the membership of a regular language in \\(AC^ 0\\) is given, thus answering the decidability question concerning this problem. Variants of the results concerning circuits with gates that compute the sum of the inputs modulo a fixed prime are considered as well.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1191027$B0596A96-A7AB-4994-822D-30CCCE940559","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1191027$F3FFB5E3-4CE7-402C-AA7E-817D43094DEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1191027$A9946B77-1D40-4580-8565-701E9977CE97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1191027$91E1F5C1-EC38-4532-B21B-B97D3CEB62C7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dd76b55f1c7bcf6e3cf9380eb723b3aefa058655","datavalue":{"value":"58912","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1191027$C6F62328-1E8E-4828-8D96-CF050DC4C336","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7142d39c3323636bd7cc377526eabf4365b5d436","datavalue":{"value":"regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1191027$EEBC4C1D-4BDF-41C4-8C1E-D88D566C43CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42057bfaccb223b82ed61e893f5ddcd54f694fa7","datavalue":{"value":"syntactic monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1191027$63C9A27B-4A9C-406C-9345-5068D69540FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"795cc5a887f77fb4c5102dea0c2c9ea7a924ca69","datavalue":{"value":"circuit complexity class","type":"string"},"datatype":"string"},"type":"statement","id":"Q1191027$FBE3E325-F025-4E1E-986A-63683E3CD06A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$0C59483F-3627-4A45-988A-E7570CDF61FF","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":"Q1191027$6DC64DA7-832C-4B24-BA3D-DBEB7F876FDB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"957892286a77298fd7faca30f1f60dbb53f94696","datavalue":{"value":{"entity-type":"item","numeric-id":1054720,"id":"Q1054720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$B188220A-DFC5-4427-AC72-3CE171DFC575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85332f45c574807884e55f6488cd3b450f276a8f","datavalue":{"value":{"entity-type":"item","numeric-id":1117696,"id":"Q1117696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$CDB2DD07-4E5E-4976-B129-66CAE1ABCDEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5592afdbc278531a8faff3dfe5516c2b3be670a","datavalue":{"value":{"entity-type":"item","numeric-id":2640342,"id":"Q2640342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$1E9B5E6C-3475-401F-81FF-D696EC92A157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a500206698011a9fd73535b39e18690c6e06e392","datavalue":{"value":{"entity-type":"item","numeric-id":3820014,"id":"Q3820014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$B8DE312C-AE42-498A-94AB-4E89D1F8F254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c42f3454db729f5c2d10bdc9af7e7e883687f9d","datavalue":{"value":{"entity-type":"item","numeric-id":804303,"id":"Q804303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$6A9272AA-34CC-4287-88FC-A6C80F288F49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2299871f8da3ff873a8d3556c58e2f6c60e4e2b9","datavalue":{"value":{"entity-type":"item","numeric-id":1242697,"id":"Q1242697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$C6725E37-0330-4323-A701-4C430A3EB387","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"465c44674a94414cb55e7dc8cbdf974e7462af9b","datavalue":{"value":{"entity-type":"item","numeric-id":3287248,"id":"Q3287248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$83D8E9AA-5947-4437-B984-B7AA0956D95C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc52fd070face52feaef752bb83efe70a407c41b","datavalue":{"value":{"entity-type":"item","numeric-id":1083202,"id":"Q1083202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$A2ADE908-053A-4220-82E4-FDBCE14B26FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3aa57810f0528ce2438cd0f484c242c53bb4e54","datavalue":{"value":{"entity-type":"item","numeric-id":3325043,"id":"Q3325043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$E20AF12B-F680-4772-9C70-FAEDE4C8A242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daa28b36f1d47ef725ba4acb380f1839600a6b45","datavalue":{"value":{"entity-type":"item","numeric-id":4132170,"id":"Q4132170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$E25F938D-E2BE-4131-9EEE-A417D143490F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e39951d487d3bf563c62341ed381ea5be4f484","datavalue":{"value":{"entity-type":"item","numeric-id":3318683,"id":"Q3318683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$8091FD12-567E-4BCB-B91F-935CC90AF30E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04ca7a1acbb96c14c8f84c4ce6e6462daf757716","datavalue":{"value":{"entity-type":"item","numeric-id":3773337,"id":"Q3773337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$A7762463-C17B-4030-998E-B96E44E6B64F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afe18fdfb882c799d34a7482b763d96a45625e71","datavalue":{"value":{"entity-type":"item","numeric-id":3853827,"id":"Q3853827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$2FA696FB-0F80-46A8-BB52-F397B070FCAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2dd225cb7a1f1b5d01838e5961bac1df864370d","datavalue":{"value":{"entity-type":"item","numeric-id":5641083,"id":"Q5641083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$87FCC5C5-D982-46D3-9E50-5FA0F457DEB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed68160731cf55d219ba94647825683328472c30","datavalue":{"value":{"entity-type":"item","numeric-id":3769981,"id":"Q3769981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$84C7C38D-1B07-42EE-BEC7-3ADF4F60FE33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ffb7c4897464eade24b984dc253233d6968fb77","datavalue":{"value":{"entity-type":"item","numeric-id":1095871,"id":"Q1095871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$00BA07FC-31EB-4EB9-AE74-3AC34C382270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98554b277242125c67fbb359aa4c54ca22c25d4c","datavalue":{"value":{"entity-type":"item","numeric-id":5339335,"id":"Q5339335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$34FB1C37-EBEF-425F-AA2C-9AC6AF68AFC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c9844351f58878ba449a8fd8cf45bb4cc809d46","datavalue":{"value":{"entity-type":"item","numeric-id":599182,"id":"Q599182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$93158B6D-F8F7-45B2-87DB-3B433A054704","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d30c038c48bc81b8cae35cb9ffa29dd01bf8f223","datavalue":{"value":{"entity-type":"item","numeric-id":1257988,"id":"Q1257988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$5961C483-35E6-492F-9FE6-58F3B331C6F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3626f68b3e5ec0492e6a80f03a49c491f73d2757","datavalue":{"value":{"entity-type":"item","numeric-id":3806849,"id":"Q3806849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$939011C0-C319-4D27-8C54-700377BC8D8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14aab8a219d2c63fceedf1ddaf5823f03d020cc7","datavalue":{"value":{"entity-type":"item","numeric-id":5750404,"id":"Q5750404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$ACFDD1BE-6D79-4A1A-94C5-9581C30A51D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aee6d83667516f08e057d913a2b054f4d07e596f","datavalue":{"value":{"entity-type":"item","numeric-id":1173413,"id":"Q1173413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$A5DC0A13-3B27-4F84-9B1C-8C8F9A781DD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4106ee1359f86fe88fb498711e75cf06db6594e","datavalue":{"value":{"entity-type":"item","numeric-id":581545,"id":"Q581545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1191027$BA479CE0-92F8-469A-A65D-2E49047689C1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"76656a2aace6dfe9cb4e29eb9b25d682a7520069","datavalue":{"value":"https://doi.org/10.1016/0022-0000(92)90014-a","type":"string"},"datatype":"url"},"type":"statement","id":"Q1191027$37F4539E-E106-4C52-97C7-ED22C7987184","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b8523fce6039f9ea968df600493757467e3d2731","datavalue":{"value":"W1972594149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1191027$A11D650E-2746-4643-A046-2627DEA0CFFC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e48b6f157a81bed9468780f4eb73ab534e6e9822","datavalue":{"value":{"entity-type":"item","numeric-id":5425344,"id":"Q5425344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbe5debae9b694244fd716e369333c49d5d8988a","datavalue":{"value":{"amount":"+0.864192008972168","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":"Q1191027$9F0845F6-D130-4A1F-8959-04B31F7A59AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e49aef1ee9eaf235afe8b5153c603784894acd6c","datavalue":{"value":{"entity-type":"item","numeric-id":5895106,"id":"Q5895106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d43d0e29fe092fc40c83380968d1af3b04c64c98","datavalue":{"value":{"amount":"+0.8476871252059937","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":"Q1191027$E25D9FEA-A9AF-429A-81C0-C3C7F11F3B6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bf05e43be3d590f9ea26689032ba01901fd6c86","datavalue":{"value":{"entity-type":"item","numeric-id":1193413,"id":"Q1193413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a60dcc4deb4e8632b22e3758588f61d73e5a0ef1","datavalue":{"value":{"amount":"+0.8397229909896851","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":"Q1191027$45B414F3-7570-4CAC-B5BC-32BA1A2D5D4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc1a0ddbe660e16818a12ecf1d6377c8afe25028","datavalue":{"value":{"entity-type":"item","numeric-id":3123635,"id":"Q3123635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a956124ef27ee102a5cf17e6e86c91c19939b2a","datavalue":{"value":{"amount":"+0.835778534412384","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":"Q1191027$3B9B5629-BB90-48E7-9C1A-6A0FB1759953","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d089c7a24a2446b8683482421b7be1b17a159706","datavalue":{"value":{"entity-type":"item","numeric-id":5918477,"id":"Q5918477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e10a771c82046d421575722e2f8adc01e7160ac","datavalue":{"value":{"amount":"+0.8190873861312866","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":"Q1191027$ED4EB5B9-8118-4603-9CC4-01E9FA179490","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Regular languages in \\(NC\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Regular_languages_in_%5C(NC%5C)"}}}}}