Inference of deterministic one-counter languages

DOI10.1016/0020-0255(84)90048-3MaRDI QIDQ794442zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 1984

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0255(84)90048-3

zbMATH Keywords

computation tracesdeterministic one- counter automatadeterministic one-counter languagesenumerationgrammatical inferenceidentification in the limitinference algorithms

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.

Recommendations

• Learning Regular Languages Using Nondeterministic Finite Automata
• Inference of finite automata using homing sequences
• A Family of Algorithms for Non Deterministic Regular Languages Inference
• scientific article; zbMATH DE number 67617
• scientific article; zbMATH DE number 4060763

Cites work

• A solution of the syntactical induction-inference problem for regular languages
• Deterministic one-counter automata
• Grammar enumeration and inference
• Grammatical Inference: Introduction and Survey - Part II
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3407175 (Why is no real title available?)
• Inference of Reversible Languages
• Language identification in the limit
• System identification via state characterization

Cited in

(4)

• One-counter automata for parsing and language approximation
• One-way permutations and self-witnessing languages
• Grammatical Inference: Algorithms and Applications
• Deciding determinism of unary languages

This page was built for publication: Inference of deterministic one-counter languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q794442)