On a structural property in the state complexity of projected regular languages
type: Item
instance of: scholarly article
title: On a structural property in the state complexity of projected regular languages
zbMATH Open document ID: 1276.68093
author: Galina Jirásková
author: Tomáš Masopust
published in: Theoretical Computer Science
publication date: 2012-08-13T00:00:00Z
review text: 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.
reviewed by: Giovanni Pighizzini
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6065033
zbMATH Keywords: finite automata
zbMATH Keywords: projections
zbMATH Keywords: state complexity
zbMATH Keywords: descriptional complexity
describes a project that uses: UMDES
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.04.009
OpenAlex ID: W1964746886
cites work: Determination of finite automata accepting subregular languages
cites work: Introduction to Discrete Event Systems
cites work: On the computation of natural observers in discrete-event systems
cites work: Compositional Verification in Supervisory Control
cites work: Magic numbers in the state hierarchy of finite automata
cites work: The magic number problem for subregular language families
cites work: Q3102144
cites work: Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
cites work: A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
cites work: DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET
cites work: Q4779161
cites work: On the State Complexity of Complements, Stars, and Reversals of Regular Languages
cites work: MAGIC NUMBERS AND TERNARY ALPHABET
cites work: Complexity in union-free regular languages
cites work: State Complexity of Projected Languages
cites work: Synthesis of controllable and normal sublanguages for discrete-event systems using a coordinator
cites work: Supervisory control synthesis of discrete-event systems using a coordination scheme
cites work: Coordination Control of Distributed Discrete-Event Systems
cites work: Q5554980
cites work: Q5586371
cites work: On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
cites work: Control of distributed systems: tutorial and overview
cites work: Q3392273
DOI: 10.1016/J.TCS.2012.04.009
description: scientific article; zbMATH DE number 6065033