The theory of finite automata (FA) is extensively studied, while Zadeh’s sets and fuzzy logic address real-world scenarios. This paper formalizes fuzzy automata’s behavior in dealing with uncertainty and vagueness inherent to computational problems. It assigns formal semantics to these languages by integrating fuzziness into transitions/states and allowing arbitrary actions to execute synchronously, resulting in new product automata.

Heyting automata, a variant of fuzzy automata with transitions having truth values from a Heyting algebra, generate Heyting synchronous languages. A Kleene algebra is defined using a Heyting algebra and a Heyting synchronous language. Similar to FA, regular expressions are derived from a Heyting automaton via state elimination, producing an automaton with a single transition labeled with action α. Hoare’s concurrency operator (’||’) models parallel execution, while the ⊕-operator captures uncertainty in parallel actions. Generalizing synchronous languages with embedded weight accommodates both synchronous execution and vagueness in transitions.

Contrary to deterministic FA, a Heyting automata’s input alphabet Σ comprises (symbol, weight), with the transition function δ mapping (state, alphabet, state) to weight. An automata recognizes a word w if its weight is equal to or greater than hs(w), computed by the function hs. The deterministic FA is a subclass of Heyting automata.

In summary, the paper introduces a new class of automata, capturing both vagueness and synchronicity and fulfilling the semantic structure for fuzzy Arden syntax. It suggests expanding the field to compute execution steps and resource consumption in computational processes.