Minimization, characterizations, and nondeterminism for biautomata
Minimization, characterizations, and nondeterminism for biautomata
We show how to minimize biautomata with a Brzozowski-like algorithm by applying reversal and powerset construction twice. Biautomata were recently introduced in[O. Klíma, L. Polák: On biautomata. RAIRO Theor. Inf. Appl., 46(4), 2012] as a generalization of ordinary finite automata, reading the input from both sides. The correctness of the Brzozowski-like minimization algorithm needs a little bit more argumentation than for ordinary finite automata since for a biautomaton its dual or reverse automaton, built by reversing all transitions, does not necessarily accept the reversal of the original language. To this end we first generalize the notion of biautomata to deal with nondeterminism and moreover, to take structural properties of the forward- and backward-transition of the automaton into account. This results in a variety of biautomata models, which accepting power is characterized. As a byproduct we give a simple structural characterization of cyclic regular and commutative regular languages in terms of deterministic biautomata.
- Justus Liebig University Giessen Germany
ddc:004, Data processing Computer science, cyclic languages, 511, commutative languages, Routing and layout, Parallel rewriting systems (e.g., developmental systems, L-systems), Grammars and Other Rewriting Systems (D.3.1), Grammar types (e.g., context-free, context-sensitive), Relations among complexity classes, Decision problems, Pattern matching, Thue systems, Complexity of proof procedures, Parsing, Machine-independent complexity**, Brzozowski´s minimization algorithm, deterministic and nondeterministic biautomata, Reducibility and completeness, Geometrical problems and computations, Relations among complexity measures, Computations on discrete structures, Sorting and searching, Sequencing and scheduling, Complexity hierarchies, Complexity Measures and Classes (F.2) (REVISED), Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3), ddc: ddc:004
ddc:004, Data processing Computer science, cyclic languages, 511, commutative languages, Routing and layout, Parallel rewriting systems (e.g., developmental systems, L-systems), Grammars and Other Rewriting Systems (D.3.1), Grammar types (e.g., context-free, context-sensitive), Relations among complexity classes, Decision problems, Pattern matching, Thue systems, Complexity of proof procedures, Parsing, Machine-independent complexity**, Brzozowski´s minimization algorithm, deterministic and nondeterministic biautomata, Reducibility and completeness, Geometrical problems and computations, Relations among complexity measures, Computations on discrete structures, Sorting and searching, Sequencing and scheduling, Complexity hierarchies, Complexity Measures and Classes (F.2) (REVISED), Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3), ddc: ddc:004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!