Inference of deterministic one-counter languages
type: Item
instance of: scholarly article
title: Inference of deterministic one-counter languages
zbMATH Open document ID: 0541.68051
DOI: 10.1016/0020-0255(84)90048-3
author: N. E. Zubov
published in: Information Sciences
publication date: 1984-01-01T00:00:00Z
review text: This paper presents inference algorithms, for the class of deterministic one-counter languages, that are based on enumeration methods. This method is known as ''identification in the limit''. Such algorithms must generate at least one automaton for each language of the class which recognizes this language. To generate not too many equivalent automata for each language, a method is described that enumerates DOCAs (deterministic one- counter automata) or a certain normal form in such a way that no two isomorphic DOCAs are generated. This is done by the generation of certain partitions on sets of so-called computation traces. This is a generalization of inference methods for finite-state machines. The whole inference method is organized in such a way that all automata are enumerated without final states. The determination of final states is not made till the consistency check with the sample. In the last part of the paper a modification of the above inference is described. This modification results from additional information on computation traces, that is included in the sample.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3860418
zbMATH Keywords: grammatical inference
zbMATH Keywords: inference algorithms
zbMATH Keywords: deterministic one-counter languages
zbMATH Keywords: enumeration
zbMATH Keywords: identification in the limit
zbMATH Keywords: deterministic one- counter automata
zbMATH Keywords: computation traces
MaRDI profile type: Publication
full work available at URL: 0020-0255(84)90048-3
OpenAlex ID: W2079632779
cites work: Inference of Reversible Languages
cites work: Grammatical Inference: Introduction and Survey - Part II
cites work: Language identification in the limit
cites work: System identification via state characterization
cites work: Q4198075
cites work: A solution of the syntactical induction-inference problem for regular languages
cites work: Q5672194
cites work: Deterministic one-counter automata
cites work: Grammar enumeration and inference
description: scientific article; zbMATH DE number 3860418