We first summarize the results on decision problen1s for FMAs. The studied problems are memb rship and non-emptiness for nondet rministic finite-m mory automata as well as for their deterministic counterpart. Given any finite automata, it can be con
sidered as an FMA in which each register is occupied by an alphab t symbol. Thu , inPquivalence prohlPm is obviou ly log-space r ducibl to -.EQ.
On the other hand the NP-hardness for DFMA inequival nc is an analogy with the reduction from SAT to it. In this reduction on side of DFMAs is fixed to ace pt the D*. The other DFMA is reduced from a given Boolean formula in conjunctiv normal form. he two DFMAs are not equal iff th CNF is satisfiable. All the results obtained are listed in Tabl 4.1.
I
membershipI
non-SDFMA P-compl t NP-complete NP-hard DFMA P-complete NP-compl t NP-hard FMA NP-complete NP-compl te PSPACE-hard
Table
4.1:
The compl xity of d ci ion problems.The entry "SDFMA" denotes simpl DFMA. We note that all FMAs in the re
ductions proved are also simpl . Thus, the results for DFMAs hold on SDFMAs, too.
Looking at Table 4.1, we conclude that there is strong evidence that FMAs are more compact representation for r gular languages than finite automata unless P = NP.
As for such a compactness, a DFA and a DFMA are illustrated in F igure 4.11. The D FA accepts th language LE over 2::; =
{a, b,
C1d},
where w E LE iff there exists a permutation 1r : 2::; ---+ such that 1r( w)
=abed.
Since the number of permutations is exactly n! for n =II II,
the number of states of such a DFA increases exponentially, but the rat of increase for the corresponding DFMA is proportional to n.1,2,3,4
Initial assignment: ####
F igure 4.11: Comparing the number of stat of a DFA and a DFMA.
The membership probl ms for deterministic and nondeterministic finite automata are in DLOG and NLOG. Th problems for determini tic and nondeterministic finite
memory automata shift to P and P, respectiv ly. Thus the intractability of thes problems is concluded. Similarly, th intractability of the non- mptiness problem for
FMAs is also concluded.
Moreover, the non-emptiness problem for both deterministic and nondeterministic finite automata are DLOG§ and NLOG-complet , respectively. Therefore, these prob
lems seem to have a different complexity. How v r, the same probl ms for both FMAs and DFMAs have the sam complexity.
§The DLOG-completeness is shown under NC1 reduction.
nfortunately, neither in quivalence and inclusion problems are known to be de
cidable. Th in quivalence problem and inclusion problems are, given two FMAs to decid whether th languages of them are not equal and whether the language of one of them is in lud d by the other, respectively. We know only the result that the inclusion problem is dccidabl if one side of FMAs is deterministic and is re tricted to be of at n1ost two regisL rs ( cf.
[32]).
As w have hown in Section 4.3, for any simple DFMA
A
and B we can simulate all configuration of them on v ry string by a "polynomial-sized' alphabet. Thus, the in quival nc problem for SDFMAs is in PSPACE. Another problem that remains in this chapter i wh Lh r or not the inequivalence problem for SDFMAs is PSPACE-hard or ven in NP as well as for DFMAs.W shortly discuss the possible complexity of the problem. Since the number of distinct configurations of an FMA depends on the length of an initial assignm nt rather than on the nondeterministic transition relation, it se ms that a DFMA has also exponentially many configurations. This is even true if the input alphabet is finite. The l ngth of the string guessed to be in the symmetrical difference is expected to be expon ntial. Thus, it seems that -.EQD do s not belong to P.
N xt, we studied the learnability of simple DFMAs. We hav chosen the query learning n1od 1 introduced by Angluin
[6]
u ing m mbership and equivalence orad s for providing a fir t answ r to this problem. While an wering m mbership queries has to b con idered as an unobj ctionable ability to be requir d of a teacher, our procedure to output a count r xample for equival nc of any two SDFMAs considerably supports our viewpoint that quivalence queri for simpl DFMAs ar also reasonabl . Additionally the insight obtained in solving th equival nc probl m turned out to be helpful for designing the want d l arning algorithm.
Nevertheless, several problems remain open. Obviously the most interesting ques
tion is wheth r or not our results ar gen ralizable to the case of FMAs. Inspecting our proofs we see that almost all results obtain d h avily d pend on the following closure property: for every simpl DFMA
A
and ev ry automorphism f: n -+ n, it holds thatf(L(A))
=L(A).
This closure property is cone rned with initial assignments of simple DFMAs including only the distinguish d symbol �· However, an initial assignment of an FMA may contain any alphabet symbol. Wh n an FMA r ads an input symbolcontained in its initial assignment, it may pay special attention to this symbol con1-pared with oth r symbols not contained initially in its assignment. In this sense, every symbol is fairly judged by simple DFMAs but not by general DFMAs.
On th other hand, ther is no other difference between definitions of DFMAs and simple DFMAs except their initial assignments. Thus, we conjecture that the problem of learning the whol class of DFMAs is reducible to task of identifying initial assignm nts. We already made some progress along this line, but the final solution could not b obtained yet.
CHAPTER 5
Learning One- Variable Patterns
The consist ncy problem for on -variable patterns is in NP, but neither its NP-completeness nor its polynomial-time decidability has be n proved.
In this s ns , this probl m has something in common with testing primality.
In case of primality, given a natural number, we can decide in determinis
tic polynomial ti1n whether it is a prime assuming Riemann's hypothesis.
Howev r, in case of the consistency problem, nothing is known to be a match for Ri mann's hypothesis. This chapter deals with the computa
tional compl xity of th con i t n y problem and variants thereof.
This chapter deals with the problem of finding a consistent one-variable pattern from incomplete positive and negative examples. The tudied problems are called an extension E a consistent ext nsion CE and a robust ext nsion RE, r spectively. Problem
E corresponds to the ordinary probl m to d cid wh ther there exists a one-variable pattern that is consistent with th given positiv and negative examples.
As for the other problems, an example string is allowed to contain some unsettled symbols that can pot ntially match with very con tant symbol. For the problem
CE, one has to decide whether there xists a suitable assignm nt for these unsettled symbols as well as a one-variable pattern consistent with the exampl s with respect to the assignment chosen.
Problem RE is the universal version of problem CE, that is, now one has to decide whether ther exists a on -variable pattern that is consistent with the examples under every assignment for the unsettl d symbols.
The problems CE and RE are defined by using wild cards in positive and negative examples. Each wild card is allowed to match with every constant symbol. The
computational complexity of E, CE, and RE is studied as well as of restricted versions of these probl n1s. The restrict d problems are obtained by not allowing wild cards in the positive xampl s, while the negative examples may contain wild cards.
The d cision problems defined are closely connected to the consistent learnability of on -variabl pattern languag s from positive and negative examples. It is shown that E and restricted c are computationally equivalent, and all other problems are NP-con1pl te.