0000000000315794

AUTHOR

Rosa Montalbano

showing 4 related works from this author

Deterministic generalized automata

1995

A generalized automaton (GA) is a finite automaton where the single transitions are defined on words rather than on single letters. Generalized automata were considered by K. Hashiguchi who proved that the problem of calculating the size of a minimal GA is decidable.

Discrete mathematicsDeterministic automatonTimed automatonQuantum finite automataBüchi automatonTwo-way deterministic finite automatonNondeterministic finite automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesComputer Science::Formal Languages and Automata TheoryMobile automatonMathematics
researchProduct

Local automata and completion

1993

The problem of completing a finite automata preserving its properties is here investigated in the case of deterministic local automata. We show a decision procedure and give an algorithm which complete a deterministic local automaton (if the completion exists) with another one, having the same number of states.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESNested wordTheoretical computer scienceComputer scienceTimed automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonDFA minimizationAutomata theoryQuantum finite automataNondeterministic finite automatonComputer Science::Formal Languages and Automata Theory
researchProduct

Block-Deterministic Regular Languages

2001

We introduce the notions of blocked, block-marked and blockdeterministic regular expressions. We characterize block-deterministic regular expressions with deterministic Glushkov block automata. The results can be viewed as a generalization of the characterization of one-unambiguous regular expressions with deterministic Glushkov automata. In addition, when a language L has a block-deterministic expression E, we can construct a deterministic finite-state automaton for L that has size linear in the size of E.

Deterministic pushdown automatonDiscrete mathematicsDeterministic finite automatonNested wordDeterministic automatonDeterministic context-free grammarQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct

ON THE STAR HEIGHT OF RATIONAL LANGUAGES

1994

Two problems concerning the star height of a rational language are investigated: the star height one problem and the relationships between the unambiguity of an expression and its star height. For this purpose we consider the class of factorial, transitive and rational (FTR) languages. From the algebraic point of view a FTR language is the set of factors of a rational submonoid M. Two subclasses of FTR languages are introduced: renewal languages, corresponding to the case of M finitely generated, and unambiguous renewal languages, corresponding to the case of M finitely generated and free. We prove that a FTR language has star height one if and only if it is renewal. This gives a simple de…

Discrete mathematicsFactorialTransitive relationStar heightGeneral Mathematicsmedia_common.quotation_subjectComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)AmbiguityRegular languageIf and only ifComputer Science::Programming LanguagesEntropy (information theory)Algebraic numberMathematicsmedia_commonInternational Journal of Algebra and Computation
researchProduct