{"entities":{"Q443744":{"pageid":445511,"ns":120,"title":"Item:Q443744","lastrevid":51526679,"modified":"2026-01-18T15:41:34Z","type":"item","id":"Q443744","labels":{"en":{"language":"en","value":"On a structural property in the state complexity of projected regular languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6065033"}},"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":"Q443744$478AF2D3-8921-4E1E-B6A9-960FBDAA2581","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c0499fc17e3d7d0254cc506ab47aaafb2e242ac","datavalue":{"value":{"text":"On a structural property in the state complexity of projected regular languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q443744$5120DFF0-3830-4388-AA4A-1FE3B183A995","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cd515c2fcaa813aefdcacf3f29a840e5b59d7dfe","datavalue":{"value":"1276.68093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q443744$B5E9EB4D-5BEE-4399-9E13-6830169D5393","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c7c5967ae26e9b631724c0e0067976453948e02","datavalue":{"value":{"entity-type":"item","numeric-id":443741,"id":"Q443741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$5F701575-7A4E-450E-A11B-D59F105F3A5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4168584ba9f841bdae0fff555c40c6b9e10448b5","datavalue":{"value":{"entity-type":"item","numeric-id":414884,"id":"Q414884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$E2240BF7-19EC-46F1-B6BB-99A9BFECF596","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":"Q443744$5235E849-1762-4538-8446-11B66248C802","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8ebe7fa7a2c02a55022632020f273bc460922804","datavalue":{"value":{"time":"+2012-08-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q443744$B5937843-48C4-4C05-9F54-05398244ECBA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9806bf509ea4cb22e320b69109a83be229c47cab","datavalue":{"value":"Finite automata are useful tools for modeling systems: input symbols represent events that can occur in a system and change its status. Usually ``real'' systems have a huge number of states and, hence, the corresponding automata, even if finite, cannot be depicted in a readable and useful way. Many times, however, people are interested in considering not all possible events, but to emphasize only some of them, considering the remaining as internal changes. This leads to the investigation of so-called projected regular languages: from a language \\(L\\) over an alphabet \\(\\Sigma\\), the projected language over \\(\\Sigma_0\\subseteq\\Sigma\\) is the language obtained by removing from each string of \\(L\\) the symbols not belonging to \\(\\Sigma_0\\). Clearly, this operation preservers regularity. If \\(L\\) is accepted by a deterministic automaton with \\(n\\) states, what can be said about the states of the minimal deterministic automaton accepting the projection of~\\(L\\)? Using standard techniques it can be proved that this ``simplification'' in the alphabet can lead to an exponential increase in the number of states. In the paper under review, tight upper bounds for the state complexity of the projection are stated. In particular, these bounds are obtained by taking into account the number of states of the minimal deterministic automaton accepting the given language \\(L\\), together with the number of states which are incident with the transitions which become unobservable. The paper also present some interesting future lines of research on the topic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q443744$6B22E48E-F164-4FAC-AEA9-AA32A587883C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"587e5c2f64101fc1378a0c55968776d5385845dc","datavalue":{"value":{"entity-type":"item","numeric-id":383364,"id":"Q383364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$5AB0C80A-0535-4D0C-85D1-6E3D5BAA5456","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q443744$7C5261CC-E5BD-445F-8761-90E942811F6F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8134362cb017fefb61ef38507e2586aab51a590f","datavalue":{"value":"6065033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q443744$BC5EA663-D9A6-4D94-B3E3-1E173C1EFB52","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q443744$B60F231B-8F36-4D6D-85A9-B6842BA941E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af61ebf07455b491078594b026930b3701f75079","datavalue":{"value":"projections","type":"string"},"datatype":"string"},"type":"statement","id":"Q443744$171E3948-D8FD-491E-B88B-93912BFC71E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b10ab4d2fc75823309415cc3027a505ded7b2f","datavalue":{"value":"state complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q443744$E4BC6AA6-4B9E-4811-9881-A7D1B192F8AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6b3ac5948a51082073fe08b55937180405a1900","datavalue":{"value":"descriptional complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q443744$9F24A50C-3594-48A4-B319-76112B479176","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"effde5e7952b6c039193783c2cbc91b00b07031c","datavalue":{"value":{"entity-type":"item","numeric-id":21504,"id":"Q21504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$C438127A-1581-489E-93B2-52B3FA867B9C","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":"Q443744$7A521920-5804-43DF-93E5-1B3967194EAC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b6aab313f6cf8070d59b38f6698a9ee6fdaed037","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2012.04.009","type":"string"},"datatype":"url"},"type":"statement","id":"Q443744$C75BAC3B-B337-4AB1-A05E-69ECED6FB733","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3d73ec9cbbf0f990f3d467e8d1974c10e5df5c8a","datavalue":{"value":"W1964746886","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q443744$3D63C6A4-A8D4-4358-889F-BCF7361A8301","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a4301cfd9c19886d1e53746958dca45ae0df160","datavalue":{"value":{"entity-type":"item","numeric-id":2271457,"id":"Q2271457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$8FF9FF4B-F5BD-4346-B1C0-AC4D1CA116E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"320b15d7d6dca3e65a884cf3843d25afdc3e50e2","datavalue":{"value":{"entity-type":"item","numeric-id":3426554,"id":"Q3426554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$E47FE515-61DA-472F-AAA6-195BBD864EC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dae51a19d8bf2bd6e60ff8b2707579e82de223d9","datavalue":{"value":{"entity-type":"item","numeric-id":5962024,"id":"Q5962024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$9B1AFA6F-B1C9-41A6-ADD7-551CB4C9A340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"814223f4bd4da30f448d5d1b2c41b51941fa97b6","datavalue":{"value":{"entity-type":"item","numeric-id":3566992,"id":"Q3566992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$37F31126-4CCB-44AC-A30E-20195DC1AE47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b934c3926eea17215bbea1ed0c0439dfabebe7f5","datavalue":{"value":{"entity-type":"item","numeric-id":2461796,"id":"Q2461796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$FD6DD32B-F455-4DB6-9F30-832D16DB74A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a465b23b38728c1bc8e98c0319277bdd2f253899","datavalue":{"value":{"entity-type":"item","numeric-id":2909186,"id":"Q2909186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$9BB0D155-D4EE-46BB-AA21-A27E63E99D0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84024d594973ff8e971980ddb8d142a5250b40e7","datavalue":{"value":{"entity-type":"item","numeric-id":3102144,"id":"Q3102144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$30D22471-679A-4BD8-9A8F-2CA59F591877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e2dc714e624f2e8cf7fb6648c41bc481a890f0a","datavalue":{"value":{"entity-type":"item","numeric-id":1566750,"id":"Q1566750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$C3ACC555-2247-4B64-ABBB-7AC41CD7E61C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ba865e78a398a7e4798cfd3e1377f16c13bfaff","datavalue":{"value":{"entity-type":"item","numeric-id":1400001,"id":"Q1400001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$9AC5C165-54A2-48A6-9523-45E90516D415","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ab041a8503478f2496154c7d450372fd9baba72","datavalue":{"value":{"entity-type":"item","numeric-id":3538853,"id":"Q3538853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$5D5CC8AE-7207-4E9E-A6AE-DE6B6E233F4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65d80f7ae67e86eeec1afc01bf64ab53dd271473","datavalue":{"value":{"entity-type":"item","numeric-id":4779161,"id":"Q4779161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$B2117B7F-9840-4D82-A653-482BEE2D3948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c56e006b9fe278713f23d0c7e75c883a085e1c5f","datavalue":{"value":{"entity-type":"item","numeric-id":3533030,"id":"Q3533030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$041C1D97-696C-4EBA-AEC2-014D47494B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"033ac08505892cf7b1cbf5d7735780fee58654d1","datavalue":{"value":{"entity-type":"item","numeric-id":3086242,"id":"Q3086242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$382E5E87-4D6B-49DC-8519-5297E4CED232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"899cecbbc44a042a21e531c43a22bd6af743a33f","datavalue":{"value":{"entity-type":"item","numeric-id":2909101,"id":"Q2909101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$2C4618D9-6FF4-430C-95FC-1004CAC26B74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2048f57bdf6fd66dff56ef1dc87cb0c42ea1a562","datavalue":{"value":{"entity-type":"item","numeric-id":5200092,"id":"Q5200092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$687AAE09-F84B-4315-8660-0E387DF9AA33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ccb55cd86222448da7a5f46c9987ae63d8aac8b","datavalue":{"value":{"entity-type":"item","numeric-id":553375,"id":"Q553375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$21E604A6-E4EA-4431-8042-89A15575E79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"258e111e518aad597ace79bf1f5f0da726abb142","datavalue":{"value":{"entity-type":"item","numeric-id":1941245,"id":"Q1941245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$FDBE401E-10A5-48D7-A4FE-A78F1C026BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21255eca0d1a4d3685682399be50254c21702822","datavalue":{"value":{"entity-type":"item","numeric-id":5496926,"id":"Q5496926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$668ED78F-59A3-425D-BECF-20E4AEF07D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"735238b3e7c7f03ab1fec1b4302c31439ded9b9c","datavalue":{"value":{"entity-type":"item","numeric-id":5554980,"id":"Q5554980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$2E98B618-FFAB-42E2-9C68-6993F3AEA8DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"211b8c9c7cfa745da39b5cfdefa1164357c9f908","datavalue":{"value":{"entity-type":"item","numeric-id":5586371,"id":"Q5586371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$C192C51C-5FD5-4144-B726-8082892E2B78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71af02a11f0cbe069e4ea9beb45ae622432bd444","datavalue":{"value":{"entity-type":"item","numeric-id":5638224,"id":"Q5638224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$69FFDA71-F40D-44ED-9122-CD9C250B775A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c14671132a92d24ed4e7003d561b5b5b9a59b98e","datavalue":{"value":{"entity-type":"item","numeric-id":693692,"id":"Q693692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$CEE18594-3CE7-4BCD-83FD-F946B772FE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a34f4e568c2469f8063f69f8c16802976e475eb9","datavalue":{"value":{"entity-type":"item","numeric-id":3392273,"id":"Q3392273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q443744$510ADC48-BF85-41B6-AAAD-093869D3DDAC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"70725a462e71c509494fce3c64f029ea3c30a173","datavalue":{"value":"10.1016/J.TCS.2012.04.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q443744$3CAF79A4-3F91-439C-8663-B4C8837AECD1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6e79cd46e72b19485f0683790660907aa83a510","datavalue":{"value":{"entity-type":"item","numeric-id":5200092,"id":"Q5200092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32ba8bec475704149cfe4c262859afff62ad7183","datavalue":{"value":{"amount":"+0.9084147810935974","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":"Q443744$BFA76CD8-7589-49AF-9231-902BBFED5EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12c22035c34340500e16ffc962e379dee64cda9a","datavalue":{"value":{"entity-type":"item","numeric-id":2915168,"id":"Q2915168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b893290624d3e36b1eb7afb3ff9000b72d5a24b5","datavalue":{"value":{"amount":"+0.8443012237548828","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":"Q443744$91231D45-6982-4CDE-9C47-3FE3B696E0A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40923da50dd065de190563a14918bf2a8f97ba1b","datavalue":{"value":{"entity-type":"item","numeric-id":2731279,"id":"Q2731279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6abbb98ff8161e073274e8a5c8810b9db4c224c4","datavalue":{"value":{"amount":"+0.771552324295044","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":"Q443744$533F0B79-F538-4FF9-9004-91C8292ACA8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e51f2ead10c7d2a3d43a91075669533e452b0cf","datavalue":{"value":{"entity-type":"item","numeric-id":1318694,"id":"Q1318694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5762b9cc60b66538599bb45d7dfb434f4be2fa2","datavalue":{"value":{"amount":"+0.7474455833435059","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":"Q443744$10B79A30-1108-441E-BAAD-814BE5892022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"013c91945fdf2c1ac39eaa126fe1b5cdce13583f","datavalue":{"value":{"entity-type":"item","numeric-id":3655366,"id":"Q3655366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64abc1790540c5c537bccd273d7813d7e347de68","datavalue":{"value":{"amount":"+0.7466174960136414","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":"Q443744$726F789C-064F-468D-BEE0-0A75EBD51C62","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:443744","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:443744"}}}}}