Pumping lemma in automata theory based on complete residuated lattice-valued logic: a note

DOI10.1016/J.FSS.2006.03.014MaRDI QIDQ853474zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Daowen Qiu

Publication date 15 November 2006

Published in Fuzzy Sets and Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.fss.2006.03.014

zbMATH Keywords

fuzzy automatalattice theorymany-valued logicnonclassical logicpumping lemma

Mathematics Subject Classification ID

Many-valued logic (03B50) Fuzzy logic; logic of vagueness (03B52) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45) General topics in artificial intelligence (68T01)

Review text

Using the framework of fuzzy finite automata theory, the author continues earlier work on residuated lattice-valued logic to prove interesting results on an analogue of the standard pumping lemma from classical automata theory. In the process, the author provides a partial solution to a difficult 1952 problem by J. B. Rosser and A. R. Turquette, viz., if there exist many-valued logics beyond the level of predicate logic (it turn out that they do exist), what is the nature of such theories? The author's approach has several deep applications to artificial intelligence techniques.

Recommendations

• Pumping Lemma in context-free grammar theory based on complete residuated lattice-valued logic
• Automata theory based on complete residuated lattice-valued logic
• Automata theory based on complete residuated lattice-valued logic: Pushdown automata
• A comment on ``Automata theory based on complete residuated lattice-valued logic: pushdown automata
• Automata theory based on quantum logic. II.

Cites work

• Abstract residuation over lattices
• Automata theory based on complete residuated lattice-valued logic
• Automata theory based on complete residuated lattice-valued logic. II
• Axiom schemes for m-valued propositions calculi
• Deterministic Acceptors of Regular Fuzzy Languages
• Efficient simulation of finite automata by neural nets
• Fuzzifying topology based on complete residuated lattice-valued logic. I
• Fuzzy discrete structures
• Fuzzy sets and systems. Theory and applications
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1862743 (Why is no real title available?)
• scientific article; zbMATH DE number 3307592 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3392404 (Why is no real title available?)
• scientific article; zbMATH DE number 3414288 (Why is no real title available?)
• Linear logic
• Maximin automata
• On Fuzzy Logic I Many‐valued rules of inference
• On Fuzzy Logic II. Enriched residuated lattices and semantics of propositional calculi
• On Fuzzy Logic III. Semantical completeness of some many‐valued propositional calculi

Cited in

(56)

• Automata theory based on complete residuated lattice-valued logic: Pushdown automata
• Pumping Lemma in context-free grammar theory based on complete residuated lattice-valued logic
• Grammar theory based on lattice-ordered monoid
• Automata theory based on complete residuated lattice-valued logic: a categorical approach
• Lattice-valued fuzzy Turing machines: computing power, universality and efficiency
• Coding tree languages based on lattice-valued logic
• Construction of fuzzy automata from fuzzy regular expressions
• Characterizations of complete residuated lattice-valued finite tree automata
• A comment on ``Automata theory based on complete residuated lattice-valued logic: pushdown automata
• Fuzzy grammar theory based on lattices
• Fuzzy multiset finite automata and their languages
• Determinization of fuzzy automata by factorizations of fuzzy states and right invariant fuzzy quasi-orders
• Formal power series and regular operations on fuzzy languages
• Fuzzy tree language recognizability
• Simulation for lattice-valued doubly labeled transition systems
• Equivalence in automata theory based on complete residuated lattice-valued logic
• On intuitionistic fuzzy context-free languages
• Algebraic properties of complete residuated lattice valued tree automata
• Determinization of fuzzy automata with membership values in complete residuated lattices
• Similarity-based minimization of fuzzy tree automata
• Fuzzy languages with infinite range accepted by fuzzy automata: pumping lemma and determinization procedure
• Weak bisimulations for fuzzy automata
• Brzozowski type determinization for fuzzy automata
• Bisimulations for fuzzy automata
• GENERAL FUZZY AUTOMATA BASED ON COMPLETE RESIDUATED LATTICE-VALUED
• State hyperstructures of tree automata based on lattice-valued logic
• ADMISSIBLE PARTITION FOR BL-GENERAL FUZZY AUTOMATON
• TREE AUTOMATA BASED ON COMPLETE RESIDUATED LATTICE-VALUED LOGIC: REDUCTION ALGORITHM AND DECISION PROBLEMS
• Lattice-valued simulations for quantitative transition systems
• TOPOLOGICAL CHARACTERIZATION FOR FUZZY REGULAR LANGUAGES
• Lattice-Semigroups Tree Automation’s Congruence and Homomorphism
• scientific article; zbMATH DE number 7528980 (Why is no real title available?)
• Nondeterministic fuzzy automata with membership values in complete residuated lattices
• Categories of Automata and Languages Based on a Complete Residuated Lattice
• Fuzzy pushdown automata
• On the category of \(L\)-fuzzy automata, coalgebras and dialgebras
• On a factorized \(L\)-fuzzy automaton and its \(L\)-fuzzy topological characterization
• On closure properties of \(\mathcal{L}\)-valued linear languages
• On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations
• Finite automata theory with membership values in lattices
• L-fuzzy automata theory: some characterizations via general fuzzy operators
• On L-fuzzy automata, coalgebras and dialgebras: associated categories and L-fuzzy topologies
• Logical characterizations of simulation and bisimulation for fuzzy transition systems
• Further improvements of determinization methods for fuzzy finite automata
• Algebraic properties of approximate bisimulation relations for fuzzy automata
• Computation of the greatest simulations and bisimulations between fuzzy automata
• Automata theory based on complete residuated lattice-valued logic: Turing machines
• Minimization of hesitant L-fuzzy automaton.
• On compositions of (L-fuzzy) automata: a categorical approach
• Approximate bisimulations for fuzzy-transition systems
• Residuated lattice-valued automata based on graphs
• Reduction of fuzzy automata by means of fuzzy quasi-orders
• Automata theory based on complete residuated lattice-valued logic. II
• Myhill-Nerode type theory for fuzzy languages and automata
• Automata theory based on complete residuated lattice-valued logic: Reduction and minimization
• Fuzzy relation equations and reduction of fuzzy automata

This page was built for publication: Pumping lemma in automata theory based on complete residuated lattice-valued logic: a note

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