{"entities":{"Q1280234":{"pageid":1290984,"ns":120,"title":"Item:Q1280234","lastrevid":68356737,"modified":"2026-04-12T23:09:40Z","type":"item","id":"Q1280234","labels":{"en":{"language":"en","value":"The passing of a rational expression to a nondeterministic finite automaton"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1260659"}},"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":"Q1280234$63AE9D54-D790-484C-9C92-3E669D198105","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"caf1580e11c4b77ebe2bfad1fa00c14525522335","datavalue":{"value":{"text":"The passing of a rational expression to a nondeterministic finite automaton","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1280234$A1B144AC-EDC5-4EFB-ADE5-C2961C7FC36A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7e5a8507787a8405d08c3f1097a94a0668b5e80e","datavalue":{"value":"0915.68123","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280234$2575E93A-C047-40E3-AA59-C569986F914A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1707e75d31a6b2e3660e28becce082325eba1f3","datavalue":{"value":{"entity-type":"item","numeric-id":491615,"id":"Q491615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1280234$A84426B3-B282-47D7-946E-858EC0AF9F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e6d8b2726414ae4b9c090a6569372588be8ab6e3","datavalue":{"value":{"entity-type":"item","numeric-id":1280233,"id":"Q1280233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1280234$D5ABB858-487B-406D-B44D-399DF5B88488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7d834650717dd8ea4fc41e16d34de55d91424ddc","datavalue":{"value":{"entity-type":"item","numeric-id":396949,"id":"Q396949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1280234$2A28346B-3250-4B08-A52A-16F1B4D4A54A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c4f16ddc5cdb18d4f4fb3ee6d704d6609c3404ba","datavalue":{"value":{"entity-type":"item","numeric-id":223802,"id":"Q223802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1280234$09B4A1C3-F522-491C-BF38-A2402E5012C7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ccb0389d49d9dccc22d89b86cf8dea63356eb4b","datavalue":{"value":{"time":"+1999-03-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1280234$97613808-D3E4-4A4C-9253-FA3147259781","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b8fc76b2d8c1c5246218b05d0968058905717121","datavalue":{"value":"https://eudml.org/doc/119810","type":"string"},"datatype":"url"},"type":"statement","id":"Q1280234$F5A66E99-F8B0-41CB-987E-5070D1684866","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21fd3100341fe59147d3c2bf487f2162831264bf","datavalue":{"value":"Let but de cet article est de pr\u00e9senter un nouvel algorithme s\u00e9quentiel en temps \\(\\Omega(n^2)\\) pour la conversion d'une expression rationnelle simple, ayant \\(n\\) occurrences de symboles, en son automate de Glushkov (automate d'\u00e9tats finis, non n\u00e9cessairement d\u00e9terministe, sans \\(\\varepsilon\\)-transitions, ayant \\(n+1\\) \u00e9tats, repr\u00e9sent\u00e9 par sa table de transitions).   Les algorithmes produits par A. Br\u00fcggemann-Klein et par C. H. Chang et R. Paige \u00e9valuent les op\u00e9rations de fermeture (\u00e9toile de Kleene) en unions (d'ensembles de transitions) disjointes, selon les deux variantes suivantes:  \\[ \\delta\\uplus A= (\\delta\\setminus(\\delta\\cap A))\\cup A= \\delta\\cup(A\\setminus(\\delta\\cap A)). \\]  A. Br\u00fcggemann-Klein introduit la notion de ``Star Normal form'' (forme normale de fermeture) et calcule ``au plus tard'' les transitions induites par un op\u00e9rateur de fermeture. Chang et Paige \u00e9valuent de fa\u00e7on paresseuse la fonction de transitions avec une structure de donn\u00e9es appel\u00e9e CNNFA (Compressed Normal NFA) \u00e0 base de for\u00eats d'\u00e9tats.   \u00c0 complexit\u00e9 temporelle \u00e9gale, notre algorithme est in\u0165eressant pour les raisons suivantes. Tout d'abord il repose sur une repr\u00e9sentation originale de l'automate de Glushkov, bas\u00e9e sur des for\u00eats d'\u00e9tas diff\u00e9rentes de celles de Chang et Paige. Le passage de l'expression \u00e0 cette repr\u00e9sentation de l'automate est en temps lin\u00e9aire par rapport au nombre d'occurrences de lettres \\(n\\); la traduction en table de transitions est en \\(\\Omega(n^2)\\). L\u00e9valuation des op\u00e9rations de fermeture sur cette repr\u00e9sentation est r\u00e9alis\u00e9e en unions disjointes par un algorithme r\u00e9cursif original en temps lin\u00e9aire par rapport \u00e0 \\(n\\). Par ailleurs, cet algorithme s\u00e9quentiel se pr\u00eate bien \u00e0 la parall\u00e9lisation dans le mod\u00e8le PRAM.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1280234$EF988FD1-11F1-48F5-BDC0-339F600043CB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280234$49B15EC9-7CE4-486A-9639-66A1970A3FB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"24aafcf24a21bd70cd3b62d3f5f72a6d0d82d816","datavalue":{"value":"68-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280234$DEEF1EDD-E26F-48B6-9C01-ACDE6E53B42D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed293b811733fa9438a72e1b6ba5680a0d2aac9e","datavalue":{"value":"68-06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280234$5E99A00B-0F37-43FD-995E-BFCE85E35C32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280234$E237EBDC-D6FF-4F59-B71B-4CD7A0C558A5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"207c2c73253315162869012ff838d1976543905d","datavalue":{"value":"1260659","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280234$A09AF78C-1112-4CAF-826F-EFF3698C104C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a670297fb7782ef83457beb8f2176ba4dcbe7c0c","datavalue":{"value":"nondeterministic finite automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1280234$7B7F882B-C581-4BFD-AC29-3D526D986989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7c105b9df034687aa1ee423419ea0a503343f89","datavalue":{"value":"star normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q1280234$CB55EFCE-CED6-4AD7-907C-C8C07B7FF67D","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":"Q1280234$9C73AC42-B62D-49CC-A336-519D12503617","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3021997bdbcfc6436486cb9a0d138bd319c6137b","datavalue":{"value":{"entity-type":"item","numeric-id":1285572,"id":"Q1285572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41bbb7b437cc82a808fcb9896a19a8320c7de6e9","datavalue":{"value":{"amount":"+0.831703782081604","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":"Q1280234$01D30B2B-C815-448B-932D-83391005FE55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83b235a936aefc5a4eac490fac643662319f4ba4","datavalue":{"value":{"entity-type":"item","numeric-id":1314367,"id":"Q1314367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09cee6a8201d4f914ae4ee7d5d4083a3b37e4bf2","datavalue":{"value":{"amount":"+0.8276800513267517","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":"Q1280234$B10FB146-5A46-4F8D-A188-9BF8DBC3AB44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53cbbf2058d9ef8c914ae041e338f368d52a20b9","datavalue":{"value":{"entity-type":"item","numeric-id":1575946,"id":"Q1575946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"641bc2664ce2ba8b2de295a2c18fbb2f934fd201","datavalue":{"value":{"amount":"+0.8270545601844788","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":"Q1280234$2F12E3F3-80D9-47A2-AE5E-3E5BB98D0CB5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The passing of a rational expression to a nondeterministic finite automaton","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_passing_of_a_rational_expression_to_a_nondeterministic_finite_automaton"}}}}}