The Complexity of Ehrenfeucht-Fra¨ısse´ Games

Get Complete Project Material File(s) Now! »

The complexity of Ehrenfeucht-Fra¨ısse´ games

This chapter focuses on ﬁnite structures. We address the eﬃciency of deciding the winners of Ehrenfeucht-Fra¨ısse´ games for some standard classes of ﬁnite structures. An Ehrenfeucht-Fra¨ısse´ game (EF game for short) is a two-player game played on two structures A and B of the same signature. We call the two players of the game respectively Spoiler and Duplicator. For a natural number n ∈ N, the n-round EF-game on A and B, denoted by Gn(A,B), is played by the two players moving in n rounds. At each round, Spoiler selects structure A or B, and then selects an element from the selected structure. Then, Duplicator responds by selecting an element from the other structure. Hence over a sequence of n rounds, the players produce a sequence a1,…,an of elements in A and a sequence b1,…,bn of elements in B such that for 1 ≤ i ≤ n, (ai,bi) is the pair of elements selectedbytheplayersinroundi. Duplicatorwinstheplayifthemappingai → bi,i = 1,…,n, is a partial isomorphism between A and B. Duplicator wins the game Gn(A,B) if she can always select elements in a way that wins the play regardless of the sequence of elements that Spoiler selects. Informally, Duplicator’s goal is to show that the two structures A and B are “similar”, while Spoiler needs to show the opposite. It is clear that when A and B are isomorphic, Duplicator wins Gn(A,B) for all n ∈ N. On the other hand, when A and B are ﬁnite structures, for large n (where n is greater or equal to the largest cardinality of A and B), if Duplicator wins the game Gn(A,B) then A and B are isomorphic. It is known that for all n ∈ N, Duplicator wins the game Gn(A,B) if and only if A and B satisfy the same ﬁrst order formulas of quantiﬁer rank n [28, 20]. Hence, these games can be viewed as a way for approximating if two structures are isomorphic. It is thus interesting to develop tools and algorithms for ﬁnding winners of EF games. Grohe [44] studied EF games with a ﬁxed number of pebbles and showed that the problem of deciding the winner is PTIME-complete. Pezzoili [94] showed that deciding the winner of EF games is PSPACE-complete. Kolaitis/Panttaja [80] proved thatthe following problem isEXPTIME-complete: given a natural number kand structuresAandB,decidethewinner for the k pebble existential EF game on A and B. Fix a natural number n ∈ N. We concern the following question that we call the n-Ehrenfeucht-Fra¨ısse´ problem.
INPUT: Two relational structures A and B from a ﬁxed class of structures QUESTION: Does Duplicator win the n-round EF game Gn(A,B)?
In this chapter, we solve the Ehrenfeucht-Fra¨ısse´ problem for the following classes of ﬁnite structures:
1. structures with only unary predicates
2. equivalence structures and their extensions
3. trees with height predicates
4. Boolean algebras with distinguished ideals
We provide algorithms for solving the Ehrenfeucht-Fra¨ısse´ problem for the structures mentioned above. The running time of all the algorithms are bounded by constants. We obtain the values of these constants as functions of n. As an example, we brieﬂy describe our result for equivalence structures, which are structures of the form (D;E) where E is an equivalence relation. For any EF game played on two equivalence structures, we deﬁne two conditions, small disparity and large disparity, each of which guarantees winning for Spoiler. We deﬁne these conditions using the numbers of equivalence classes of some particular sizes in both structures. We then prove that these conditions are necessary for Spoiler to win the EF game. To do that, assuming neither small nor large disparity occurs, we describe a strategy for Duplicator that ensures all plays satisfy some invariants at all rounds of the game. In particular, these invariants imply that the strategy is winning for Duplicator. Hence,tocomputethewinnerofanEFgameplayedonequivalence structures, it suﬃces to check if either small or large disparity occurs, which can be done in constant time under some assumptions on the representations of the structures. As a result, we obtain the following theorem:
Theorem 3.3.5. Fix n ∈ N. There existsan algorithm that runs in constanttime and decides whetherDuplicator wins the game Gn(A,B) on ﬁnite equivalence structures A and B. The constant that bounds the running time is n.
Wethenextendtheabove technique tovariants ofequivalence structures. Forexample, an equivalence structure with s colors is a structures of the type (A;E,P1,…,Ps), where E is an equivalence relation on A and P1,…,Ps are unary predicates. An embedded equivalence structure of height h is the form A = (A;E1,E2,…,Eh) such that each Ei where 1 ≤ i ≤ h is an equivalence relation and Ei ⊆ Ej for i < j. For these extended notions of equivalence structures, we deﬁne diﬀerent forms of disparities and prove that they are necessary and suﬃcient conditions for Spoiler to win the EF game.
Theorem 3.4.10. Fix n ∈ N. There exists an algorithm that runs in constant time and decides whetherDuplicator wins the n-round Ehrenfeucht-Fra¨ısse´ game Gn(A,B) on ﬁnite equivalence structures with s colors. The constant that bounds the running time is n2s+1.
Theorem 3.5.6. Fix n ∈ N. There existsan algorithm that runs in constanttime and decides whether Duplicator wins game Gn(A,B) on ﬁnite embedded equivalence structures of height h A = (A;E1,…,Eh) and B = (B;E1,…,Eh). The constant that bounds the running time is < (n + 1)…(n+1)(n+1) where the tower of (n + 1) has height h.
A tree with level predicates is a structure of the type (T;≤,L0,…,Lh) where (T;≤) is a tree of height h (where the height of a tree is the maximal number of edges along a maximal path), and for i ∈ {0,…,h}, Li is a unary predicate such that an element x ∈ T belongs to Li if and only if x has level i. The next theorem is obtained using a reduction from the EF game problem on embedded equivalence structures.
Theorem 3.6.2. Fix n ∈ N. There exists an algorithm that runs in constanttime and decides whetherDuplicator wins n-round Ehrenfeucht-Fra¨ısse´ game Gn(T1,T2) on ﬁnite trees with level predicates T1 and T2 of height h. The constant that bounds the running time is (n + 1)…(n+1)(n+1) where the tower has height h.
Lastly, we look at Boolean algebra with distinguished ideals, which are structures of the form (A;≤,0,1,I1,…,Is), where (A;≤,0,1) forms a Boolean algebra and each Ij is an ideal of the algebra (A;≤,0,1). When the domain A is ﬁnite, the structure A can be identiﬁed with the structure (2XA;⊆,∅,XA,2A1,…,2As), where each ideal Ii, 1 ≤ i ≤ s, is the set 2Ai.
Theorem 3.7.3. Fix n ∈ N. There exists an algorithm that runs in constant time and decides whether Duplicator wins the game Gn+1(A,B) on ﬁnite Boolean algebras A = (2XA;⊆,∅,XA,2A1,…,2As) and B = (2XB;⊆,∅,XB,2B1,…,2Bs). The constant that bounds the running time is 2s · 2n.
We summarize all these theorems in Table 1.1. Note that all the time complexity listed are independent on the sizes of the input structures.
The material of this chapter has appeared in Khoussainov/Liu [64, 65].

The complexity of unary automatic structures

This chapter analyses complexity in unary automatic structures. These are inﬁnite structures whose domain is the regular language 1⋆ and whose relations are recognized by ﬁnite automata over the unary alphabet. These structures form an intermediate class between ﬁnite structures and automatic structures in general and are interesting due to their proximity to ﬁnite structures. One of the advantages possessed by these structures over the automatic structures is the decidability of their monadic second-order theories. Many natural graph problems (such as graph connectivity and reachability) are expressible in monadic second-order logic and are hence decidable for unary automatic graphs. However, deciding these questions by a translation of MSO formulae yields very slow algorithms (super-exponential in the size of the input automatic presentations). In this chapter, we exploit structural properties of unary automatic graphs to solve these questionsinpolynomial-time. Furthermore,specialfocuswillbe putonsolvingtheisomorphism problem on a speciﬁc subclass K of unary automatic structures:
INPUT: Given the automatic presentations of two structures A and B from K QUESTION: Decide if A and B are isomorphic.
This chapter consists of ﬁve sections. The ﬁrst section introduces unary automatic structures and presents a characterization of these structures. In the second section, we study algorithms on the class of unary automatic graphs of ﬁnite degree. These are inﬁnite graphs result from a natural unfolding operation appliedtoﬁnitegraphs. Inparticular, this class of graphs corresponds exactly to the conﬁguration graphs of one-counter processes (pushdown automata with just one stack symbol). Such graphs have received increasing interests in the recent years [33, 107, 112, 32]. We are interested in the following natural decision problem on automatic graphs:
• Connectivity problem: Given an automatic graph G, decide whether G is connected.
• Reachability problem: Given an automatic graph G and two nodes x and y of G, decide whether there is a path from x to y.
• Inﬁnity testing problem: Given an automatic graph G and a node x, decide whetherthe component in G containing x is inﬁnite.
• Inﬁnite component problem: Given an automatic graph G, decide whether G has an inﬁnite component.
We present explicit algorithms for all of the problems above. The complexity of each algorithmis polynomial in termsofthe sizes ofthe inputautomata. Forexample,we prove the following results
Theorem 4.2.11. The inﬁnity testing problem for unary automatic graph of ﬁnite degree G is solved in O(n3), where n is the size of the input automaton recognizing G. In particular, when G is ﬁxed, there is a constant time algorithm that decides the inﬁnity testing problem on G.
Theorem 4.2.14. There exists an algorithm that solves the reachability problem on any unary automatic graph G of ﬁnite degree in time O(p4 + |u| + |v|) where u,v are two input nodes from the graph G and n is the size of the input automaton recognizing G.
Bouajjani/Esparza/Maler in [9, 24, 111] studied the reachability problem on the class of pushdown graphs which properly contains all unary automatic graphs. They proved that for a pushdown graph and a node v, there is an automaton Av that recognizes all nodes reachable from v. This implies decidability of the reachability problem on unary automatic graphs of ﬁnite degree. In this work, we provide an alternative algorithm that constructs a deterministic unary automaton AReach that accepts the reachability relation of a unary automatic graph G of ﬁnite degree,hence solving the reachability problem uniformly. This greatly improves the mentioned work of Bouajjani/Esparza/Maler in the class of unary automatic graphs since the automaton constructed now does not depend on the nodes v. The size of the automaton AReach depends only on the size n of the input automaton and the construction takes polynomial time on n.
Corollary 4.2.19. Given a unary automatic graph of ﬁnite degree G represented by an automaton with size n, there is a deterministic automaton AReach with at most 2n4 + n3 statesthatacceptsthereachabilityrelationofG. Furthermore,thetimerequiredtoconstruct AReach is O(n5).
Table 1.2 lists all the problems and their corresponding time complexity.
Theres tof this chapter focu sesons omenaturalsubclassesofunaryautomaticstructures such as equivalence structures, linear orders and trees and analyses the complexity of deciding the isomorphism problem on these classes of structures.
Characterizations of classes of unary automatic structures were given in Blumensath [6] and Khoussainov/Rubin [73]. These results imply that the isomorphism problem for automatic linear or dersand equivalence structure sare decidable(throughmonadicsecondorder interpretations). However, the resulting decision procedures are highly ineﬃcient (doubly- or triply-exponential). In Section 4.3 and Section 4.4, we improve the complexity by providing explicit algorithm sinlow polynomial timewithrespecttotheinputautomata.
Theorem 4.3.5. The isomorphism problem for unary automatic linear orders is decidable in quadratic time in the sizes of the input automata.
Theorem 4.4.4. The isomorphism problem for unary automatic equivalence structures is decidable in linear time in the sizes of the input automata.
In Section 4.5, we analyse unary automatic trees. We present a combinatorial characterization for the class of unary automatic trees. This characterization then leads to an algorithm for solving the isomorphism problem.
Theorem 4.5.9. The isomorphism problem for unary automatic trees is decidable in time O(n4) in the sizes of the input automata.
This chapter also contains an analysis on the state complexity of the mentioned classes of unary automatic structures. We deﬁne the state complexity of an automatic structure as the smallest number of states needed for automata to describe the domain and relations of the structure. We prove that the state complexity of unary automatic equivalence relations, linear orders and trees are all polynomial with respect to some natural representations of the structures (For each class, we explicitly describe its representation). The study of state complexity of automatic structures is a new, and hopefully fruitful, area. We obtain the mentioned complexity bounds using detailed analysis on the canonical forms of automatic presentations of structures. The analysis involves lengthy,technical and carefully designed combinatorial arguments. Inaddition,the analysis greatly in teracts with properties of underlying structures. Table 1.3 summarizes the classes of unary automatic structuresandtheircorrespondingtimecomplexityfordecidingtheisomorphismproblem..

READ Analysis of Dynamic Multi-objective Optimisation Benchmark Functions

Contents
Preface
Acknowledgements
1 Introduction
1.1 Background and motivation
1.2 Summary of results
2 Preliminaries
2.1 Structures
2.2 Theories
2.3 The arithmetic hierarchy
2.4 Automata and languages
2.5 Automatic structures and computable structures
3 The Complexity of Ehrenfeucht-Fra¨ısse´ Games
3.1 Ehrenfeucht-Fra¨ısse´ games
3.2 Simple example: structures with unary predicates
3.3 Equivalence structures
3.4 Equivalence structures with colors
3.5 Embedded equivalence structures
3.6 Trees with level predicates
3.7 Boolean algebras with distinguished ideals
4 The Complexity of Unary Automatic Structures
4.1 Unary automatic structures
4.2 Unary automatic graphs of ﬁnite degree
4.3 Unary automatic linear orders
4.4 Unary automatic equivalence structures
4.5 Unary automatic trees
5 The Isomorphism Problem for Automatic Structures
5.1 Automatic equivalence structures
5.2 Automatic trees
5.3 Computable trees of ﬁnite height
5.4 Automatic linear orders
5.5 Arithmetical isomorphisms
6 Computably Categorical Graphs with Finite Components
6.1 Computable categoricity of graphs
6.2 Examples of strongly locally ﬁnite graphs
6.3 Graphs with computable size functions
6.4 A suﬃcient condition for non-computably categoricity
6.5 ∆0 3-chain of embedded components
Bibliography
List of Notations
Index
Name Index