java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 14:54:33,322 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 14:54:33,325 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 14:54:33,338 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 14:54:33,339 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 14:54:33,340 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 14:54:33,343 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 14:54:33,345 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 14:54:33,346 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 14:54:33,348 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 14:54:33,348 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 14:54:33,349 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 14:54:33,349 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 14:54:33,350 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 14:54:33,353 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 14:54:33,354 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 14:54:33,355 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 14:54:33,365 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 14:54:33,366 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 14:54:33,367 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 14:54:33,368 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 14:54:33,372 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 14:54:33,373 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 14:54:33,373 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 14:54:33,374 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 14:54:33,374 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 14:54:33,376 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 14:54:33,377 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 14:54:33,378 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 14:54:33,378 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 14:54:33,378 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 14:54:33,379 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 14:54:33,379 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 14:54:33,383 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 14:54:33,383 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 14:54:33,384 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 14:54:33,403 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 14:54:33,403 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 14:54:33,404 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 14:54:33,404 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 14:54:33,405 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 14:54:33,405 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 14:54:33,405 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 14:54:33,405 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 14:54:33,406 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 14:54:33,406 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 14:54:33,406 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 14:54:33,406 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 14:54:33,406 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 14:54:33,406 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 14:54:33,407 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 14:54:33,408 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 14:54:33,408 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 14:54:33,408 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 14:54:33,408 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 14:54:33,409 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 14:54:33,409 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 14:54:33,454 INFO ]: Repository-Root is: /tmp [2018-06-22 14:54:33,469 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 14:54:33,474 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 14:54:33,475 INFO ]: Initializing SmtParser... [2018-06-22 14:54:33,476 INFO ]: SmtParser initialized [2018-06-22 14:54:33,476 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 [2018-06-22 14:54:33,477 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 14:54:33,571 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 unknown [2018-06-22 14:54:33,820 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 [2018-06-22 14:54:33,825 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 14:54:33,834 INFO ]: Walking toolchain with 4 elements. [2018-06-22 14:54:33,834 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 14:54:33,834 INFO ]: Initializing ChcToBoogie... [2018-06-22 14:54:33,834 INFO ]: ChcToBoogie initialized [2018-06-22 14:54:33,841 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:54:33" (1/1) ... [2018-06-22 14:54:33,887 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:54:33 Unit [2018-06-22 14:54:33,887 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 14:54:33,888 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 14:54:33,888 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 14:54:33,890 INFO ]: Boogie Preprocessor initialized [2018-06-22 14:54:33,912 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:54:33" (1/1) ... [2018-06-22 14:54:33,912 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:54:33" (1/1) ... [2018-06-22 14:54:33,920 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:54:33" (1/1) ... [2018-06-22 14:54:33,920 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:54:33" (1/1) ... [2018-06-22 14:54:33,931 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:54:33" (1/1) ... [2018-06-22 14:54:33,932 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:54:33" (1/1) ... [2018-06-22 14:54:33,938 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:54:33" (1/1) ... [2018-06-22 14:54:33,939 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 14:54:33,940 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 14:54:33,940 INFO ]: Initializing RCFGBuilder... [2018-06-22 14:54:33,940 INFO ]: RCFGBuilder initialized [2018-06-22 14:54:33,944 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:54:33" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 14:54:33,959 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 14:54:33,959 INFO ]: Found specification of procedure False [2018-06-22 14:54:33,959 INFO ]: Found implementation of procedure False [2018-06-22 14:54:33,959 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 14:54:33,959 INFO ]: Found specification of procedure state [2018-06-22 14:54:33,959 INFO ]: Found implementation of procedure state [2018-06-22 14:54:33,959 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 14:54:33,959 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 14:54:33,959 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 14:54:34,135 INFO ]: Using library mode [2018-06-22 14:54:34,136 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:54:34 BoogieIcfgContainer [2018-06-22 14:54:34,136 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 14:54:34,137 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 14:54:34,137 INFO ]: Initializing TraceAbstraction... [2018-06-22 14:54:34,140 INFO ]: TraceAbstraction initialized [2018-06-22 14:54:34,140 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:54:33" (1/3) ... [2018-06-22 14:54:34,143 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6bbf20be and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 02:54:34, skipping insertion in model container [2018-06-22 14:54:34,143 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:54:33" (2/3) ... [2018-06-22 14:54:34,144 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6bbf20be and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 02:54:34, skipping insertion in model container [2018-06-22 14:54:34,144 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:54:34" (3/3) ... [2018-06-22 14:54:34,145 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 14:54:34,153 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 14:54:34,163 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 14:54:34,207 INFO ]: Using default assertion order modulation [2018-06-22 14:54:34,207 INFO ]: Interprodecural is true [2018-06-22 14:54:34,207 INFO ]: Hoare is false [2018-06-22 14:54:34,207 INFO ]: Compute interpolants for FPandBP [2018-06-22 14:54:34,207 INFO ]: Backedges is TWOTRACK [2018-06-22 14:54:34,207 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 14:54:34,207 INFO ]: Difference is false [2018-06-22 14:54:34,208 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 14:54:34,208 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 14:54:34,220 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 14:54:34,229 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 14:54:34,229 INFO ]: Found error trace [2018-06-22 14:54:34,230 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:54:34,230 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:54:34,234 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 14:54:34,235 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:54:34,235 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:54:34,270 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:34,270 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:54:34,270 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:34,297 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:34,389 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 14:54:34,393 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 14:54:34,393 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 14:54:34,395 INFO ]: Interpolant automaton has 4 states [2018-06-22 14:54:34,411 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 14:54:34,412 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:54:34,415 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 14:54:34,529 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:54:34,529 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 14:54:34,530 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 14:54:34,531 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 14:54:34,531 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:54:34,539 INFO ]: With dead ends: 13 [2018-06-22 14:54:34,539 INFO ]: Without dead ends: 13 [2018-06-22 14:54:34,541 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:54:34,554 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 14:54:34,576 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 14:54:34,578 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 14:54:34,578 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 14:54:34,580 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 14:54:34,581 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:54:34,581 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 14:54:34,581 INFO ]: Interpolant automaton has 4 states. [2018-06-22 14:54:34,581 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 14:54:34,583 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 14:54:34,583 INFO ]: Found error trace [2018-06-22 14:54:34,583 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:54:34,583 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:54:34,583 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 14:54:34,583 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:54:34,583 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:54:34,584 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:34,584 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:54:34,584 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:34,627 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:34,800 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 14:54:34,800 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:54:34,800 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:54:34,809 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:54:34,851 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:34,860 INFO ]: Computing forward predicates... [2018-06-22 14:54:35,462 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 14:54:35,490 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:54:35,490 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 14:54:35,491 INFO ]: Interpolant automaton has 9 states [2018-06-22 14:54:35,491 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 14:54:35,491 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-22 14:54:35,491 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 14:54:35,678 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:54:35,679 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 14:54:35,679 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 14:54:35,679 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 14:54:35,679 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:54:35,680 INFO ]: With dead ends: 15 [2018-06-22 14:54:35,680 INFO ]: Without dead ends: 15 [2018-06-22 14:54:35,681 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-06-22 14:54:35,681 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 14:54:35,684 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 14:54:35,684 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 14:54:35,684 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 14:54:35,684 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 14:54:35,684 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:54:35,684 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 14:54:35,685 INFO ]: Interpolant automaton has 9 states. [2018-06-22 14:54:35,685 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 14:54:35,685 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 14:54:35,685 INFO ]: Found error trace [2018-06-22 14:54:35,685 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:54:35,685 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:54:35,686 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 14:54:35,686 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:54:35,686 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:54:35,687 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:35,687 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:54:35,687 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:35,728 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:36,079 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 14:54:36,079 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:54:36,079 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:54:36,091 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 14:54:36,139 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 14:54:36,139 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:36,142 INFO ]: Computing forward predicates... [2018-06-22 14:54:36,531 WARN ]: Spent 147.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 14:54:36,821 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 14:54:36,853 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:54:36,853 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 14:54:36,854 INFO ]: Interpolant automaton has 11 states [2018-06-22 14:54:36,854 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 14:54:36,854 INFO ]: CoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2018-06-22 14:54:36,854 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 14:54:37,271 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:54:37,271 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 14:54:37,272 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 14:54:37,272 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 14:54:37,272 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:54:37,273 INFO ]: With dead ends: 17 [2018-06-22 14:54:37,273 INFO ]: Without dead ends: 17 [2018-06-22 14:54:37,273 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=49, Invalid=107, Unknown=0, NotChecked=0, Total=156 [2018-06-22 14:54:37,273 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 14:54:37,276 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 14:54:37,276 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 14:54:37,277 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 14:54:37,277 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 14:54:37,277 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:54:37,277 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 14:54:37,277 INFO ]: Interpolant automaton has 11 states. [2018-06-22 14:54:37,277 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 14:54:37,277 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 14:54:37,277 INFO ]: Found error trace [2018-06-22 14:54:37,278 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:54:37,278 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:54:37,278 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 14:54:37,278 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:54:37,278 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:54:37,279 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:37,279 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:54:37,279 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:37,348 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:37,801 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 14:54:37,801 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:54:37,801 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:54:37,814 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 14:54:37,870 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 14:54:37,871 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:37,875 INFO ]: Computing forward predicates... [2018-06-22 14:54:38,235 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 14:54:38,264 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:54:38,264 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2018-06-22 14:54:38,264 INFO ]: Interpolant automaton has 17 states [2018-06-22 14:54:38,264 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 14:54:38,265 INFO ]: CoverageRelationStatistics Valid=47, Invalid=225, Unknown=0, NotChecked=0, Total=272 [2018-06-22 14:54:38,265 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 17 states. [2018-06-22 14:54:38,389 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 35 [2018-06-22 14:54:38,670 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:54:38,671 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 14:54:38,671 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 14:54:38,671 INFO ]: Start accepts. Automaton has 17 states. Word has length 21 [2018-06-22 14:54:38,671 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:54:38,672 INFO ]: With dead ends: 19 [2018-06-22 14:54:38,672 INFO ]: Without dead ends: 19 [2018-06-22 14:54:38,672 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=89, Invalid=331, Unknown=0, NotChecked=0, Total=420 [2018-06-22 14:54:38,672 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 14:54:38,675 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 14:54:38,675 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 14:54:38,676 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 14:54:38,676 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 14:54:38,676 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:54:38,676 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 14:54:38,676 INFO ]: Interpolant automaton has 17 states. [2018-06-22 14:54:38,676 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 14:54:38,677 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 14:54:38,677 INFO ]: Found error trace [2018-06-22 14:54:38,677 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:54:38,677 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:54:38,677 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 14:54:38,677 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:54:38,677 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:54:38,678 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:38,678 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:54:38,678 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:38,733 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:39,052 WARN ]: Spent 182.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 14:54:39,263 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 14:54:39,263 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:54:39,263 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:54:39,271 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 14:54:39,316 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 14:54:39,316 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:39,320 INFO ]: Computing forward predicates... [2018-06-22 14:54:39,882 WARN ]: Spent 338.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 31 [2018-06-22 14:54:40,032 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 17 [2018-06-22 14:54:40,186 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 14:54:40,213 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:54:40,213 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 20 [2018-06-22 14:54:40,213 INFO ]: Interpolant automaton has 20 states [2018-06-22 14:54:40,213 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 14:54:40,213 INFO ]: CoverageRelationStatistics Valid=57, Invalid=323, Unknown=0, NotChecked=0, Total=380 [2018-06-22 14:54:40,213 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 20 states. [2018-06-22 14:54:40,442 WARN ]: Spent 167.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 47 [2018-06-22 14:54:40,815 WARN ]: Spent 135.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 32 [2018-06-22 14:54:41,003 WARN ]: Spent 159.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 34 [2018-06-22 14:54:41,032 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:54:41,032 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 14:54:41,036 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 14:54:41,036 INFO ]: Start accepts. Automaton has 20 states. Word has length 25 [2018-06-22 14:54:41,036 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:54:41,037 INFO ]: With dead ends: 21 [2018-06-22 14:54:41,037 INFO ]: Without dead ends: 21 [2018-06-22 14:54:41,037 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=122, Invalid=478, Unknown=0, NotChecked=0, Total=600 [2018-06-22 14:54:41,037 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 14:54:41,040 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 14:54:41,040 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 14:54:41,041 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 14:54:41,041 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 14:54:41,041 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:54:41,041 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 14:54:41,041 INFO ]: Interpolant automaton has 20 states. [2018-06-22 14:54:41,041 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 14:54:41,042 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 14:54:41,042 INFO ]: Found error trace [2018-06-22 14:54:41,042 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:54:41,042 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:54:41,042 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 14:54:41,042 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:54:41,042 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:54:41,043 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:41,043 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:54:41,043 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:41,091 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:41,406 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 14:54:41,406 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:54:41,406 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:54:41,414 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 14:54:41,516 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 14:54:41,516 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:41,521 INFO ]: Computing forward predicates... [2018-06-22 14:54:41,994 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 14:54:42,013 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:54:42,013 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 20 [2018-06-22 14:54:42,013 INFO ]: Interpolant automaton has 20 states [2018-06-22 14:54:42,013 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 14:54:42,013 INFO ]: CoverageRelationStatistics Valid=53, Invalid=327, Unknown=0, NotChecked=0, Total=380 [2018-06-22 14:54:42,013 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 20 states. [2018-06-22 14:54:42,543 WARN ]: Spent 142.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 26 [2018-06-22 14:54:42,683 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 41 [2018-06-22 14:54:42,836 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:54:42,837 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 14:54:42,837 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 14:54:42,837 INFO ]: Start accepts. Automaton has 20 states. Word has length 29 [2018-06-22 14:54:42,837 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:54:42,838 INFO ]: With dead ends: 23 [2018-06-22 14:54:42,838 INFO ]: Without dead ends: 23 [2018-06-22 14:54:42,838 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 21 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 83 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=127, Invalid=523, Unknown=0, NotChecked=0, Total=650 [2018-06-22 14:54:42,839 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 14:54:42,842 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 14:54:42,842 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 14:54:42,842 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 14:54:42,843 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 14:54:42,843 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:54:42,843 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 14:54:42,843 INFO ]: Interpolant automaton has 20 states. [2018-06-22 14:54:42,843 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 14:54:42,845 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 14:54:42,845 INFO ]: Found error trace [2018-06-22 14:54:42,845 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:54:42,845 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:54:42,845 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 14:54:42,845 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:54:42,845 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:54:42,846 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:42,846 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:54:42,846 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:42,893 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:43,327 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 20 [2018-06-22 14:54:43,469 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 27 [2018-06-22 14:54:43,687 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 14:54:43,687 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:54:43,687 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:54:43,695 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 14:54:43,747 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 14:54:43,747 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:43,752 INFO ]: Computing forward predicates... [2018-06-22 14:54:44,141 WARN ]: Spent 303.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 32 [2018-06-22 14:54:45,735 WARN ]: Spent 1.24 s on a formula simplification. DAG size of input: 32 DAG size of output: 26 [2018-06-22 14:54:45,875 WARN ]: Spent 109.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 23 [2018-06-22 14:54:46,172 WARN ]: Spent 255.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 31 [2018-06-22 14:54:46,800 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 14:54:46,830 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:54:46,830 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 26 [2018-06-22 14:54:46,831 INFO ]: Interpolant automaton has 26 states [2018-06-22 14:54:46,831 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-22 14:54:46,831 INFO ]: CoverageRelationStatistics Valid=74, Invalid=576, Unknown=0, NotChecked=0, Total=650 [2018-06-22 14:54:46,831 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 26 states. [2018-06-22 14:54:47,639 WARN ]: Spent 703.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 76 [2018-06-22 14:54:47,908 WARN ]: Spent 177.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 27 [2018-06-22 14:54:48,058 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 28 [2018-06-22 14:54:48,303 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 34 [2018-06-22 14:54:48,583 WARN ]: Spent 247.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 27 [2018-06-22 14:54:48,915 WARN ]: Spent 305.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 34 [2018-06-22 14:54:49,245 WARN ]: Spent 303.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 35 [2018-06-22 14:54:49,274 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:54:49,275 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 14:54:49,275 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 14:54:49,275 INFO ]: Start accepts. Automaton has 26 states. Word has length 33 [2018-06-22 14:54:49,276 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:54:49,276 INFO ]: With dead ends: 25 [2018-06-22 14:54:49,276 INFO ]: Without dead ends: 25 [2018-06-22 14:54:49,277 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 143 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=191, Invalid=865, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 14:54:49,277 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 14:54:49,281 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 14:54:49,281 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 14:54:49,281 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 14:54:49,282 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 14:54:49,282 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:54:49,282 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 14:54:49,282 INFO ]: Interpolant automaton has 26 states. [2018-06-22 14:54:49,282 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 14:54:49,283 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 14:54:49,283 INFO ]: Found error trace [2018-06-22 14:54:49,283 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:54:49,283 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:54:49,283 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 14:54:49,283 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:54:49,283 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:54:49,284 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:49,284 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:54:49,284 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:54:49,354 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:49,822 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 14:54:49,822 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:54:49,822 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:54:49,828 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:54:49,887 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:54:49,894 INFO ]: Computing forward predicates... [2018-06-22 14:54:53,849 WARN ]: Spent 3.37 s on a formula simplification. DAG size of input: 518 DAG size of output: 74 [2018-06-22 14:54:54,935 WARN ]: Spent 893.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 63 [2018-06-22 14:55:04,823 WARN ]: Spent 9.25 s on a formula simplification. DAG size of input: 695 DAG size of output: 139 [2018-06-22 14:55:05,239 WARN ]: Spent 301.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 34 [2018-06-22 14:55:05,424 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 31 [2018-06-22 14:55:05,951 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 14:55:05,979 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 14:55:06,048 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 14:55:06,058 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 14:55:08,071 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 14:55:08,091 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:55:08,091 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 28 [2018-06-22 14:55:08,091 INFO ]: Interpolant automaton has 28 states [2018-06-22 14:55:08,092 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-22 14:55:08,092 INFO ]: CoverageRelationStatistics Valid=88, Invalid=668, Unknown=0, NotChecked=0, Total=756 [2018-06-22 14:55:08,092 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 28 states. [2018-06-22 14:55:10,041 WARN ]: Spent 1.84 s on a formula simplification. DAG size of input: 232 DAG size of output: 128 [2018-06-22 14:55:10,889 WARN ]: Spent 748.00 ms on a formula simplification. DAG size of input: 232 DAG size of output: 28 [2018-06-22 14:55:11,802 WARN ]: Spent 863.00 ms on a formula simplification. DAG size of input: 232 DAG size of output: 28 [2018-06-22 14:55:12,615 WARN ]: Spent 762.00 ms on a formula simplification. DAG size of input: 232 DAG size of output: 36 [2018-06-22 14:55:13,422 WARN ]: Spent 713.00 ms on a formula simplification. DAG size of input: 232 DAG size of output: 30 [2018-06-22 14:55:14,473 WARN ]: Spent 999.00 ms on a formula simplification. DAG size of input: 233 DAG size of output: 50 [2018-06-22 14:55:15,538 WARN ]: Spent 1.01 s on a formula simplification. DAG size of input: 234 DAG size of output: 37 [2018-06-22 14:55:16,820 WARN ]: Spent 1.23 s on a formula simplification. DAG size of input: 235 DAG size of output: 73 [2018-06-22 14:55:16,875 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:55:16,875 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 14:55:16,877 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 14:55:16,877 INFO ]: Start accepts. Automaton has 28 states. Word has length 37 [2018-06-22 14:55:16,877 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:55:16,878 INFO ]: With dead ends: 27 [2018-06-22 14:55:16,878 INFO ]: Without dead ends: 27 [2018-06-22 14:55:16,879 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 26 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 157 ImplicationChecksByTransitivity, 24.1s TimeCoverageRelationStatistics Valid=239, Invalid=1021, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 14:55:16,879 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 14:55:16,883 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 14:55:16,883 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 14:55:16,883 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 14:55:16,883 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 14:55:16,884 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:55:16,884 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 14:55:16,884 INFO ]: Interpolant automaton has 28 states. [2018-06-22 14:55:16,884 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 14:55:16,885 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 14:55:16,885 INFO ]: Found error trace [2018-06-22 14:55:16,885 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:55:16,885 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:55:16,885 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 8 times [2018-06-22 14:55:16,885 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:55:16,885 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:55:16,886 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:55:16,886 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:55:16,886 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:55:16,959 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:55:17,758 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 14:55:17,758 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:55:17,758 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:55:17,766 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 14:55:17,815 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 14:55:17,815 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:55:17,823 INFO ]: Computing forward predicates... [2018-06-22 14:55:23,118 WARN ]: Spent 4.83 s on a formula simplification. DAG size of input: 700 DAG size of output: 81 [2018-06-22 14:55:24,040 WARN ]: Spent 444.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 44 [2018-06-22 14:55:24,891 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 14:55:24,911 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:55:24,912 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 31 [2018-06-22 14:55:24,912 INFO ]: Interpolant automaton has 31 states [2018-06-22 14:55:24,912 INFO ]: Constructing interpolant automaton starting with 31 interpolants. [2018-06-22 14:55:24,912 INFO ]: CoverageRelationStatistics Valid=88, Invalid=842, Unknown=0, NotChecked=0, Total=930 [2018-06-22 14:55:24,913 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 31 states. [2018-06-22 14:55:25,672 WARN ]: Spent 704.00 ms on a formula simplification. DAG size of input: 131 DAG size of output: 82 [2018-06-22 14:55:26,044 WARN ]: Spent 328.00 ms on a formula simplification. DAG size of input: 129 DAG size of output: 32 [2018-06-22 14:55:26,359 WARN ]: Spent 280.00 ms on a formula simplification. DAG size of input: 131 DAG size of output: 31 [2018-06-22 14:55:26,706 WARN ]: Spent 311.00 ms on a formula simplification. DAG size of input: 131 DAG size of output: 35 [2018-06-22 14:55:27,006 WARN ]: Spent 264.00 ms on a formula simplification. DAG size of input: 131 DAG size of output: 23 [2018-06-22 14:55:27,457 WARN ]: Spent 369.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 40 [2018-06-22 14:55:27,862 WARN ]: Spent 369.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 28 [2018-06-22 14:55:28,288 WARN ]: Spent 364.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 42 [2018-06-22 14:55:28,939 WARN ]: Spent 613.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 61 [2018-06-22 14:55:28,977 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:55:28,977 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 14:55:28,977 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 14:55:28,977 INFO ]: Start accepts. Automaton has 31 states. Word has length 41 [2018-06-22 14:55:28,978 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:55:28,978 INFO ]: With dead ends: 29 [2018-06-22 14:55:28,978 INFO ]: Without dead ends: 29 [2018-06-22 14:55:28,979 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 29 SyntacticMatches, 2 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 196 ImplicationChecksByTransitivity, 10.5s TimeCoverageRelationStatistics Valid=267, Invalid=1293, Unknown=0, NotChecked=0, Total=1560 [2018-06-22 14:55:28,979 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 14:55:28,982 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 14:55:28,982 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 14:55:28,983 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 14:55:28,983 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 14:55:28,983 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:55:28,983 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 14:55:28,983 INFO ]: Interpolant automaton has 31 states. [2018-06-22 14:55:28,983 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 14:55:28,984 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 14:55:28,984 INFO ]: Found error trace [2018-06-22 14:55:28,984 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:55:28,984 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:55:28,984 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 9 times [2018-06-22 14:55:28,984 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:55:28,984 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:55:28,985 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:55:28,985 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:55:28,985 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:55:29,075 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:55:29,927 WARN ]: Spent 605.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 14 [2018-06-22 14:55:30,564 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 14:55:30,564 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:55:30,564 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:55:30,570 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 14:55:30,631 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 14:55:30,631 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:55:30,639 INFO ]: Computing forward predicates... [2018-06-22 14:55:31,579 WARN ]: Spent 813.00 ms on a formula simplification. DAG size of input: 174 DAG size of output: 49 [2018-06-22 14:55:31,807 WARN ]: Spent 183.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 37 [2018-06-22 14:55:32,468 WARN ]: Spent 578.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 53 [2018-06-22 14:55:32,663 WARN ]: Spent 142.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 31 [2018-06-22 14:55:33,056 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 14:55:33,076 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:55:33,076 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 32 [2018-06-22 14:55:33,077 INFO ]: Interpolant automaton has 32 states [2018-06-22 14:55:33,077 INFO ]: Constructing interpolant automaton starting with 32 interpolants. [2018-06-22 14:55:33,077 INFO ]: CoverageRelationStatistics Valid=103, Invalid=889, Unknown=0, NotChecked=0, Total=992 [2018-06-22 14:55:33,077 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 32 states. [2018-06-22 14:55:33,898 WARN ]: Spent 738.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 94 [2018-06-22 14:55:34,182 WARN ]: Spent 228.00 ms on a formula simplification. DAG size of input: 141 DAG size of output: 26 [2018-06-22 14:55:34,590 WARN ]: Spent 366.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 35 [2018-06-22 14:55:34,859 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 28 [2018-06-22 14:55:35,195 WARN ]: Spent 293.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 21 [2018-06-22 14:55:35,510 WARN ]: Spent 260.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 27 [2018-06-22 14:55:35,854 WARN ]: Spent 302.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 26 [2018-06-22 14:55:36,336 WARN ]: Spent 353.00 ms on a formula simplification. DAG size of input: 145 DAG size of output: 27 [2018-06-22 14:55:36,975 WARN ]: Spent 595.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 37 [2018-06-22 14:55:37,422 WARN ]: Spent 401.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 57 [2018-06-22 14:55:37,458 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:55:37,458 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 14:55:37,463 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 14:55:37,463 INFO ]: Start accepts. Automaton has 32 states. Word has length 45 [2018-06-22 14:55:37,463 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:55:37,464 INFO ]: With dead ends: 31 [2018-06-22 14:55:37,464 INFO ]: Without dead ends: 31 [2018-06-22 14:55:37,465 INFO ]: 0 DeclaredPredicates, 77 GetRequests, 31 SyntacticMatches, 5 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 262 ImplicationChecksByTransitivity, 7.6s TimeCoverageRelationStatistics Valid=314, Invalid=1492, Unknown=0, NotChecked=0, Total=1806 [2018-06-22 14:55:37,465 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 14:55:37,473 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 14:55:37,473 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 14:55:37,474 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 14:55:37,474 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 14:55:37,474 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:55:37,474 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 14:55:37,474 INFO ]: Interpolant automaton has 32 states. [2018-06-22 14:55:37,474 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 14:55:37,475 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 14:55:37,475 INFO ]: Found error trace [2018-06-22 14:55:37,475 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:55:37,475 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:55:37,475 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 10 times [2018-06-22 14:55:37,475 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:55:37,475 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:55:37,476 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:55:37,476 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:55:37,476 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:55:37,624 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:55:37,890 WARN ]: Spent 108.00 ms on a formula simplification that was a NOOP. DAG size: 4 Received shutdown request... [2018-06-22 14:55:38,250 WARN ]: Removed 6 from assertion stack [2018-06-22 14:55:38,250 WARN ]: Verification canceled [2018-06-22 14:55:38,255 WARN ]: Timeout [2018-06-22 14:55:38,255 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 02:55:38 BoogieIcfgContainer [2018-06-22 14:55:38,255 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 14:55:38,257 INFO ]: Toolchain (without parser) took 64430.18 ms. Allocated memory was 306.7 MB in the beginning and 828.4 MB in the end (delta: 521.7 MB). Free memory was 260.1 MB in the beginning and 515.8 MB in the end (delta: -255.7 MB). Peak memory consumption was 266.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:55:38,258 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 306.7 MB. Free memory is still 272.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 14:55:38,258 INFO ]: ChcToBoogie took 53.06 ms. Allocated memory is still 306.7 MB. Free memory was 260.1 MB in the beginning and 258.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:55:38,259 INFO ]: Boogie Preprocessor took 51.94 ms. Allocated memory is still 306.7 MB. Free memory was 258.1 MB in the beginning and 257.1 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-22 14:55:38,259 INFO ]: RCFGBuilder took 195.86 ms. Allocated memory is still 306.7 MB. Free memory was 257.1 MB in the beginning and 248.1 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:55:38,259 INFO ]: TraceAbstraction took 64117.53 ms. Allocated memory was 306.7 MB in the beginning and 828.4 MB in the end (delta: 521.7 MB). Free memory was 248.1 MB in the beginning and 515.8 MB in the end (delta: -267.7 MB). Peak memory consumption was 254.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:55:38,267 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 306.7 MB. Free memory is still 272.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 53.06 ms. Allocated memory is still 306.7 MB. Free memory was 260.1 MB in the beginning and 258.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 51.94 ms. Allocated memory is still 306.7 MB. Free memory was 258.1 MB in the beginning and 257.1 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 195.86 ms. Allocated memory is still 306.7 MB. Free memory was 257.1 MB in the beginning and 248.1 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 64117.53 ms. Allocated memory was 306.7 MB in the beginning and 828.4 MB in the end (delta: 521.7 MB). Free memory was 248.1 MB in the beginning and 515.8 MB in the end (delta: -267.7 MB). Peak memory consumption was 254.0 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 50 with TraceHistMax 11, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 30. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 64.0s OverallTime, 11 OverallIterations, 11 TraceHistogramMax, 22.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 138 SDtfs, 508 SDslu, 979 SDs, 0 SdLazy, 861 SolverSat, 603 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 437 GetRequests, 191 SyntacticMatches, 13 SemanticMatches, 233 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 990 ImplicationChecksByTransitivity, 53.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=31occurred in iteration=10, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 10 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 39.1s InterpolantComputationTime, 531 NumberOfCodeBlocks, 531 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 512 ConstructedInterpolants, 0 QuantifiedInterpolants, 108785240 SizeOfPredicates, 611 NumberOfNonLiveVariables, 1926 ConjunctsInSsa, 451 ConjunctsInUnsatCore, 19 InterpolantComputations, 1 PerfectInterpolantSequences, 330/1230 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig05.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_14-55-38-281.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig05.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_14-55-38-281.csv Completed graceful shutdown