java -Xss1g -Xmx8000000000 -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-comp18-benchmarks/lia/chc-lia-0061.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-20 23:06:19,739 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-20 23:06:19,748 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-20 23:06:19,762 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-20 23:06:19,762 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-20 23:06:19,763 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-20 23:06:19,764 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-20 23:06:19,765 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-20 23:06:19,767 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-20 23:06:19,768 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-20 23:06:19,768 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-20 23:06:19,769 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-20 23:06:19,770 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-20 23:06:19,771 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-20 23:06:19,771 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-20 23:06:19,774 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-20 23:06:19,776 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-20 23:06:19,790 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-20 23:06:19,793 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-20 23:06:19,794 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-20 23:06:19,796 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-20 23:06:19,798 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-20 23:06:19,798 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-20 23:06:19,798 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-20 23:06:19,799 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-20 23:06:19,800 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-20 23:06:19,801 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-20 23:06:19,801 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-20 23:06:19,808 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-20 23:06:19,808 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-20 23:06:19,809 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-20 23:06:19,809 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-20 23:06:19,810 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-20 23:06:19,810 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-20 23:06:19,811 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-20 23:06:19,811 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-20 23:06:19,843 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-20 23:06:19,844 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-20 23:06:19,844 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-20 23:06:19,844 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-20 23:06:19,845 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-20 23:06:19,846 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-20 23:06:19,846 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-20 23:06:19,846 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-20 23:06:19,846 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-20 23:06:19,846 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-20 23:06:19,847 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-20 23:06:19,847 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-20 23:06:19,847 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-20 23:06:19,847 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-20 23:06:19,848 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-20 23:06:19,848 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-20 23:06:19,848 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-20 23:06:19,848 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-20 23:06:19,848 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-20 23:06:19,850 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-20 23:06:19,850 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-20 23:06:19,895 INFO ]: Repository-Root is: /tmp [2018-06-20 23:06:19,966 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-20 23:06:19,974 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-20 23:06:19,975 INFO ]: Initializing SmtParser... [2018-06-20 23:06:19,976 INFO ]: SmtParser initialized [2018-06-20 23:06:19,976 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp18-benchmarks/lia/chc-lia-0061.smt2 [2018-06-20 23:06:19,979 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-20 23:06:20,074 INFO ]: Executing SMT file /storage/chc-comp18-benchmarks/lia/chc-lia-0061.smt2 unknown [2018-06-20 23:06:20,269 INFO ]: Succesfully executed SMT file /storage/chc-comp18-benchmarks/lia/chc-lia-0061.smt2 [2018-06-20 23:06:20,274 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-20 23:06:21,022 INFO ]: Walking toolchain with 4 elements. [2018-06-20 23:06:21,022 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-20 23:06:21,022 INFO ]: Initializing ChcToBoogie... [2018-06-20 23:06:21,022 INFO ]: ChcToBoogie initialized [2018-06-20 23:06:21,027 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 20.06 11:06:20" (1/1) ... [2018-06-20 23:06:21,072 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:06:21 Unit [2018-06-20 23:06:21,072 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-20 23:06:21,073 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-20 23:06:21,073 INFO ]: Initializing Boogie Preprocessor... [2018-06-20 23:06:21,073 INFO ]: Boogie Preprocessor initialized [2018-06-20 23:06:21,100 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:06:21" (1/1) ... [2018-06-20 23:06:21,100 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:06:21" (1/1) ... [2018-06-20 23:06:21,110 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:06:21" (1/1) ... [2018-06-20 23:06:21,111 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:06:21" (1/1) ... [2018-06-20 23:06:21,115 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:06:21" (1/1) ... [2018-06-20 23:06:21,121 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:06:21" (1/1) ... [2018-06-20 23:06:21,122 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:06:21" (1/1) ... [2018-06-20 23:06:21,134 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-20 23:06:21,134 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-20 23:06:21,135 INFO ]: Initializing RCFGBuilder... [2018-06-20 23:06:21,135 INFO ]: RCFGBuilder initialized [2018-06-20 23:06:21,136 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:06:21" (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-20 23:06:21,154 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-20 23:06:21,154 INFO ]: Found specification of procedure False [2018-06-20 23:06:21,154 INFO ]: Found implementation of procedure False [2018-06-20 23:06:21,154 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-20 23:06:21,154 INFO ]: Found specification of procedure state [2018-06-20 23:06:21,154 INFO ]: Found implementation of procedure state [2018-06-20 23:06:21,154 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-20 23:06:21,154 INFO ]: Found specification of procedure Ultimate.START [2018-06-20 23:06:21,154 INFO ]: Found implementation of procedure Ultimate.START [2018-06-20 23:06:21,356 INFO ]: Using library mode [2018-06-20 23:06:21,356 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.06 11:06:21 BoogieIcfgContainer [2018-06-20 23:06:21,356 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-20 23:06:21,358 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-20 23:06:21,358 INFO ]: Initializing TraceAbstraction... [2018-06-20 23:06:21,361 INFO ]: TraceAbstraction initialized [2018-06-20 23:06:21,361 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 20.06 11:06:20" (1/3) ... [2018-06-20 23:06:21,362 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@297527ee and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 20.06 11:06:21, skipping insertion in model container [2018-06-20 23:06:21,362 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:06:21" (2/3) ... [2018-06-20 23:06:21,362 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@297527ee and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.06 11:06:21, skipping insertion in model container [2018-06-20 23:06:21,362 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.06 11:06:21" (3/3) ... [2018-06-20 23:06:21,364 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-20 23:06:21,373 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-20 23:06:21,379 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-20 23:06:21,420 INFO ]: Using default assertion order modulation [2018-06-20 23:06:21,420 INFO ]: Interprodecural is true [2018-06-20 23:06:21,420 INFO ]: Hoare is false [2018-06-20 23:06:21,420 INFO ]: Compute interpolants for FPandBP [2018-06-20 23:06:21,421 INFO ]: Backedges is TWOTRACK [2018-06-20 23:06:21,421 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-20 23:06:21,421 INFO ]: Difference is false [2018-06-20 23:06:21,421 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-20 23:06:21,421 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-20 23:06:21,435 INFO ]: Start isEmpty. Operand 13 states. [2018-06-20 23:06:21,444 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-20 23:06:21,444 INFO ]: Found error trace [2018-06-20 23:06:21,445 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:06:21,445 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:06:21,449 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-20 23:06:21,451 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:06:21,451 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:06:21,488 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:21,488 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 23:06:21,488 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:21,519 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:21,608 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 23:06:21,610 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-20 23:06:21,610 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-20 23:06:21,612 INFO ]: Interpolant automaton has 4 states [2018-06-20 23:06:21,622 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-20 23:06:21,622 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-20 23:06:21,624 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-20 23:06:21,706 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:06:21,706 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-20 23:06:21,707 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-20 23:06:21,708 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-20 23:06:21,708 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:06:21,717 INFO ]: With dead ends: 13 [2018-06-20 23:06:21,717 INFO ]: Without dead ends: 13 [2018-06-20 23:06:21,719 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-20 23:06:21,732 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-20 23:06:21,751 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-20 23:06:21,752 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-20 23:06:21,752 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-20 23:06:21,753 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-20 23:06:21,753 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:06:21,753 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-20 23:06:21,753 INFO ]: Interpolant automaton has 4 states. [2018-06-20 23:06:21,753 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-20 23:06:21,754 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-20 23:06:21,754 INFO ]: Found error trace [2018-06-20 23:06:21,754 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:06:21,754 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:06:21,754 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-20 23:06:21,755 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:06:21,755 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:06:21,755 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:21,755 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 23:06:21,755 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:21,783 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:22,032 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-20 23:06:22,032 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:06:22,032 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-20 23:06:22,039 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 23:06:22,063 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:22,076 INFO ]: Computing forward predicates... [2018-06-20 23:06:22,355 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-20 23:06:22,399 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:06:22,399 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-20 23:06:22,400 INFO ]: Interpolant automaton has 6 states [2018-06-20 23:06:22,400 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-20 23:06:22,400 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-20 23:06:22,400 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-20 23:06:22,570 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:06:22,571 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-20 23:06:22,572 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-20 23:06:22,572 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-20 23:06:22,572 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:06:22,572 INFO ]: With dead ends: 15 [2018-06-20 23:06:22,572 INFO ]: Without dead ends: 15 [2018-06-20 23:06:22,573 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-20 23:06:22,573 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-20 23:06:22,576 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-20 23:06:22,576 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-20 23:06:22,577 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-20 23:06:22,577 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-20 23:06:22,577 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:06:22,577 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-20 23:06:22,577 INFO ]: Interpolant automaton has 6 states. [2018-06-20 23:06:22,577 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-20 23:06:22,578 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-20 23:06:22,578 INFO ]: Found error trace [2018-06-20 23:06:22,578 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:06:22,578 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:06:22,578 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-20 23:06:22,578 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:06:22,578 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:06:22,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:22,579 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 23:06:22,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:22,639 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:22,888 WARN ]: Spent 129.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-20 23:06:23,101 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-20 23:06:23,101 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:06:23,101 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-20 23:06:23,110 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-20 23:06:23,168 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-20 23:06:23,168 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:23,171 INFO ]: Computing forward predicates... [2018-06-20 23:06:23,339 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-20 23:06:23,364 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:06:23,364 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-20 23:06:23,364 INFO ]: Interpolant automaton has 8 states [2018-06-20 23:06:23,365 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-20 23:06:23,365 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-20 23:06:23,365 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 8 states. [2018-06-20 23:06:23,724 WARN ]: Spent 209.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-20 23:06:24,021 WARN ]: Spent 275.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 15 [2018-06-20 23:06:24,130 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:06:24,130 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-20 23:06:24,132 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-20 23:06:24,132 INFO ]: Start accepts. Automaton has 8 states. Word has length 17 [2018-06-20 23:06:24,132 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:06:24,132 INFO ]: With dead ends: 17 [2018-06-20 23:06:24,132 INFO ]: Without dead ends: 17 [2018-06-20 23:06:24,133 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2018-06-20 23:06:24,133 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-20 23:06:24,136 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-20 23:06:24,136 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-20 23:06:24,136 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-20 23:06:24,136 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-20 23:06:24,136 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:06:24,136 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-20 23:06:24,136 INFO ]: Interpolant automaton has 8 states. [2018-06-20 23:06:24,137 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-20 23:06:24,142 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-20 23:06:24,142 INFO ]: Found error trace [2018-06-20 23:06:24,142 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:06:24,142 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:06:24,143 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-20 23:06:24,143 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:06:24,143 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:06:24,143 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:24,144 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 23:06:24,144 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:24,189 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:24,577 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-20 23:06:24,577 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:06:24,577 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-20 23:06:24,590 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-20 23:06:24,629 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-20 23:06:24,630 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:24,633 INFO ]: Computing forward predicates... [2018-06-20 23:06:24,819 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-20 23:06:24,849 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:06:24,849 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-20 23:06:24,849 INFO ]: Interpolant automaton has 10 states [2018-06-20 23:06:24,850 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-20 23:06:24,850 INFO ]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-06-20 23:06:24,850 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 10 states. [2018-06-20 23:06:25,125 WARN ]: Spent 247.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 19 [2018-06-20 23:06:25,379 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:06:25,379 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-20 23:06:25,380 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-20 23:06:25,380 INFO ]: Start accepts. Automaton has 10 states. Word has length 21 [2018-06-20 23:06:25,380 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:06:25,381 INFO ]: With dead ends: 19 [2018-06-20 23:06:25,381 INFO ]: Without dead ends: 19 [2018-06-20 23:06:25,381 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=56, Invalid=126, Unknown=0, NotChecked=0, Total=182 [2018-06-20 23:06:25,381 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-20 23:06:25,388 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-20 23:06:25,388 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-20 23:06:25,389 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-20 23:06:25,389 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-20 23:06:25,389 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:06:25,389 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-20 23:06:25,389 INFO ]: Interpolant automaton has 10 states. [2018-06-20 23:06:25,389 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-20 23:06:25,390 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-20 23:06:25,390 INFO ]: Found error trace [2018-06-20 23:06:25,390 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:06:25,390 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:06:25,390 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-20 23:06:25,390 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:06:25,390 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:06:25,391 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:25,391 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 23:06:25,391 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:25,460 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:25,715 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-20 23:06:25,715 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:06:25,715 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-20 23:06:25,732 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-20 23:06:25,778 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-20 23:06:25,778 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:25,782 INFO ]: Computing forward predicates... [2018-06-20 23:06:26,508 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-20 23:06:26,528 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:06:26,528 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 14 [2018-06-20 23:06:26,528 INFO ]: Interpolant automaton has 14 states [2018-06-20 23:06:26,528 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-20 23:06:26,528 INFO ]: CoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2018-06-20 23:06:26,528 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 14 states. [2018-06-20 23:06:26,961 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 22 [2018-06-20 23:06:27,205 WARN ]: Spent 222.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 30 [2018-06-20 23:06:27,258 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:06:27,258 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-20 23:06:27,258 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-20 23:06:27,258 INFO ]: Start accepts. Automaton has 14 states. Word has length 25 [2018-06-20 23:06:27,258 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:06:27,259 INFO ]: With dead ends: 21 [2018-06-20 23:06:27,259 INFO ]: Without dead ends: 21 [2018-06-20 23:06:27,259 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=87, Invalid=255, Unknown=0, NotChecked=0, Total=342 [2018-06-20 23:06:27,259 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-20 23:06:27,262 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-20 23:06:27,262 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-20 23:06:27,263 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-20 23:06:27,263 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-20 23:06:27,263 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:06:27,263 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-20 23:06:27,263 INFO ]: Interpolant automaton has 14 states. [2018-06-20 23:06:27,263 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-20 23:06:27,265 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-20 23:06:27,265 INFO ]: Found error trace [2018-06-20 23:06:27,265 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:06:27,265 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:06:27,266 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-20 23:06:27,266 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:06:27,266 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:06:27,266 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:27,266 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 23:06:27,266 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:27,303 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:27,565 WARN ]: Spent 152.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 34 [2018-06-20 23:06:27,850 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-20 23:06:27,850 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:06:27,850 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-20 23:06:27,863 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-20 23:06:27,927 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-20 23:06:27,927 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:27,931 INFO ]: Computing forward predicates... [2018-06-20 23:06:28,371 WARN ]: Spent 372.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 29 [2018-06-20 23:06:28,587 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 31 [2018-06-20 23:06:29,115 WARN ]: Spent 244.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 20 [2018-06-20 23:06:29,827 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-20 23:06:29,861 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:06:29,861 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 21 [2018-06-20 23:06:29,862 INFO ]: Interpolant automaton has 21 states [2018-06-20 23:06:29,862 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-20 23:06:29,862 INFO ]: CoverageRelationStatistics Valid=61, Invalid=359, Unknown=0, NotChecked=0, Total=420 [2018-06-20 23:06:29,862 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 21 states. [2018-06-20 23:06:32,736 WARN ]: Spent 2.32 s on a formula simplification. DAG size of input: 68 DAG size of output: 68 [2018-06-20 23:06:32,880 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 29 [2018-06-20 23:06:33,048 WARN ]: Spent 146.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 35 [2018-06-20 23:06:33,436 WARN ]: Spent 364.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 59 [2018-06-20 23:06:33,886 WARN ]: Spent 420.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 51 [2018-06-20 23:06:34,236 WARN ]: Spent 280.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 68 [2018-06-20 23:06:34,319 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:06:34,319 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-20 23:06:34,320 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-20 23:06:34,320 INFO ]: Start accepts. Automaton has 21 states. Word has length 29 [2018-06-20 23:06:34,320 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:06:34,321 INFO ]: With dead ends: 23 [2018-06-20 23:06:34,321 INFO ]: Without dead ends: 23 [2018-06-20 23:06:34,321 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 97 ImplicationChecksByTransitivity, 5.6s TimeCoverageRelationStatistics Valid=148, Invalid=554, Unknown=0, NotChecked=0, Total=702 [2018-06-20 23:06:34,321 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-20 23:06:34,325 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-20 23:06:34,325 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-20 23:06:34,325 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-20 23:06:34,325 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-20 23:06:34,326 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:06:34,326 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-20 23:06:34,326 INFO ]: Interpolant automaton has 21 states. [2018-06-20 23:06:34,326 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-20 23:06:34,327 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-20 23:06:34,327 INFO ]: Found error trace [2018-06-20 23:06:34,327 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:06:34,327 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:06:34,327 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-20 23:06:34,327 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:06:34,327 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:06:34,328 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:34,328 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 23:06:34,328 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:34,363 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:34,899 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-20 23:06:34,899 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:06:34,899 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-20 23:06:34,907 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-20 23:06:34,957 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-20 23:06:34,957 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:34,962 INFO ]: Computing forward predicates... [2018-06-20 23:06:35,620 WARN ]: Spent 574.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 34 [2018-06-20 23:06:36,407 WARN ]: Spent 577.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 42 [2018-06-20 23:06:36,600 WARN ]: Spent 159.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 31 [2018-06-20 23:06:36,843 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 31 [2018-06-20 23:06:37,367 WARN ]: Spent 107.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-20 23:06:37,870 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-20 23:06:37,903 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:06:37,903 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 23 [2018-06-20 23:06:37,904 INFO ]: Interpolant automaton has 23 states [2018-06-20 23:06:37,904 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-20 23:06:37,904 INFO ]: CoverageRelationStatistics Valid=67, Invalid=439, Unknown=0, NotChecked=0, Total=506 [2018-06-20 23:06:37,904 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 23 states. [2018-06-20 23:06:38,526 WARN ]: Spent 528.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 93 [2018-06-20 23:06:38,808 WARN ]: Spent 237.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 26 [2018-06-20 23:06:39,329 WARN ]: Spent 367.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-06-20 23:06:39,757 WARN ]: Spent 374.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 45 [2018-06-20 23:06:40,203 WARN ]: Spent 411.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 63 [2018-06-20 23:06:40,722 WARN ]: Spent 490.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 52 [2018-06-20 23:06:41,165 WARN ]: Spent 413.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 75 [2018-06-20 23:06:41,205 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:06:41,205 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-20 23:06:41,206 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-20 23:06:41,206 INFO ]: Start accepts. Automaton has 23 states. Word has length 33 [2018-06-20 23:06:41,206 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:06:41,207 INFO ]: With dead ends: 25 [2018-06-20 23:06:41,207 INFO ]: Without dead ends: 25 [2018-06-20 23:06:41,207 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 26 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 101 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=175, Invalid=695, Unknown=0, NotChecked=0, Total=870 [2018-06-20 23:06:41,207 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-20 23:06:41,211 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-20 23:06:41,211 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-20 23:06:41,211 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-20 23:06:41,211 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-20 23:06:41,212 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:06:41,212 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-20 23:06:41,212 INFO ]: Interpolant automaton has 23 states. [2018-06-20 23:06:41,212 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-20 23:06:41,212 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-20 23:06:41,212 INFO ]: Found error trace [2018-06-20 23:06:41,213 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:06:41,213 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:06:41,213 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-20 23:06:41,213 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:06:41,213 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:06:41,213 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:41,213 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 23:06:41,213 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:41,277 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:41,898 WARN ]: Spent 204.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 33 [2018-06-20 23:06:42,253 WARN ]: Spent 160.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 33 [2018-06-20 23:06:42,667 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-20 23:06:42,667 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:06:42,667 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-20 23:06:42,674 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 23:06:42,725 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:42,731 INFO ]: Computing forward predicates... [2018-06-20 23:06:42,877 WARN ]: Spent 117.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 24 [2018-06-20 23:06:43,348 WARN ]: Spent 287.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 43 [2018-06-20 23:06:43,998 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-20 23:06:44,019 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:06:44,022 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 25 [2018-06-20 23:06:44,022 INFO ]: Interpolant automaton has 25 states [2018-06-20 23:06:44,022 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-20 23:06:44,022 INFO ]: CoverageRelationStatistics Valid=77, Invalid=523, Unknown=0, NotChecked=0, Total=600 [2018-06-20 23:06:44,023 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 25 states. [2018-06-20 23:06:45,248 WARN ]: Spent 1.15 s on a formula simplification. DAG size of input: 125 DAG size of output: 99 [2018-06-20 23:06:45,484 WARN ]: Spent 169.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 29 [2018-06-20 23:06:45,745 WARN ]: Spent 233.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 39 [2018-06-20 23:06:46,165 WARN ]: Spent 372.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 48 [2018-06-20 23:06:46,552 WARN ]: Spent 355.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 55 [2018-06-20 23:06:47,025 WARN ]: Spent 440.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 41 [2018-06-20 23:06:47,520 WARN ]: Spent 457.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 60 [2018-06-20 23:06:48,452 WARN ]: Spent 883.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 98 [2018-06-20 23:06:48,489 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:06:48,489 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-20 23:06:48,489 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-20 23:06:48,489 INFO ]: Start accepts. Automaton has 25 states. Word has length 37 [2018-06-20 23:06:48,489 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:06:48,490 INFO ]: With dead ends: 27 [2018-06-20 23:06:48,490 INFO ]: Without dead ends: 27 [2018-06-20 23:06:48,490 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 28 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 144 ImplicationChecksByTransitivity, 6.3s TimeCoverageRelationStatistics Valid=213, Invalid=843, Unknown=0, NotChecked=0, Total=1056 [2018-06-20 23:06:48,491 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-20 23:06:48,494 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-20 23:06:48,494 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-20 23:06:48,495 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-20 23:06:48,495 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-20 23:06:48,495 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:06:48,495 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-20 23:06:48,495 INFO ]: Interpolant automaton has 25 states. [2018-06-20 23:06:48,496 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-20 23:06:48,497 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-20 23:06:48,497 INFO ]: Found error trace [2018-06-20 23:06:48,497 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:06:48,497 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:06:48,498 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 8 times [2018-06-20 23:06:48,498 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:06:48,498 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:06:48,498 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:48,498 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 23:06:48,498 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:48,540 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:49,863 WARN ]: Spent 1.08 s on a formula simplification. DAG size of input: 25 DAG size of output: 17 [2018-06-20 23:06:50,135 WARN ]: Spent 198.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 32 [2018-06-20 23:06:50,769 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-20 23:06:50,769 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:06:50,769 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-20 23:06:50,775 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-20 23:06:50,842 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-20 23:06:50,842 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:50,849 INFO ]: Computing forward predicates... [2018-06-20 23:06:51,136 WARN ]: Spent 231.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 32 [2018-06-20 23:06:51,396 WARN ]: Spent 225.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 28 [2018-06-20 23:06:51,774 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 36 [2018-06-20 23:06:51,953 WARN ]: Spent 141.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 31 [2018-06-20 23:06:53,923 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-20 23:06:53,957 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:06:53,957 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 28 [2018-06-20 23:06:53,957 INFO ]: Interpolant automaton has 28 states [2018-06-20 23:06:53,958 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-20 23:06:53,958 INFO ]: CoverageRelationStatistics Valid=79, Invalid=677, Unknown=0, NotChecked=0, Total=756 [2018-06-20 23:06:53,958 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 28 states. [2018-06-20 23:06:55,534 WARN ]: Spent 865.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 86 [2018-06-20 23:06:55,768 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 22 [2018-06-20 23:06:56,059 WARN ]: Spent 242.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 33 [2018-06-20 23:06:56,363 WARN ]: Spent 271.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 44 [2018-06-20 23:06:56,704 WARN ]: Spent 308.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 44 [2018-06-20 23:06:57,118 WARN ]: Spent 280.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 42 [2018-06-20 23:06:57,535 WARN ]: Spent 366.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 43 [2018-06-20 23:06:57,967 WARN ]: Spent 388.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 57 [2018-06-20 23:06:58,839 WARN ]: Spent 827.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 81 [2018-06-20 23:06:58,879 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:06:58,879 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-20 23:06:58,880 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-20 23:06:58,880 INFO ]: Start accepts. Automaton has 28 states. Word has length 41 [2018-06-20 23:06:58,880 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:06:58,880 INFO ]: With dead ends: 29 [2018-06-20 23:06:58,880 INFO ]: Without dead ends: 29 [2018-06-20 23:06:58,881 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 31 SyntacticMatches, 3 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 180 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=259, Invalid=1073, Unknown=0, NotChecked=0, Total=1332 [2018-06-20 23:06:58,881 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-20 23:06:58,885 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-20 23:06:58,885 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-20 23:06:58,886 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-20 23:06:58,886 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-20 23:06:58,886 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:06:58,886 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-20 23:06:58,886 INFO ]: Interpolant automaton has 28 states. [2018-06-20 23:06:58,886 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-20 23:06:58,887 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-20 23:06:58,887 INFO ]: Found error trace [2018-06-20 23:06:58,887 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:06:58,887 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:06:58,887 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 9 times [2018-06-20 23:06:58,887 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:06:58,887 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:06:58,888 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:58,888 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 23:06:58,888 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:06:58,996 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:06:59,846 WARN ]: Spent 525.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 28 [2018-06-20 23:07:00,076 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 37 [2018-06-20 23:07:00,430 WARN ]: Spent 148.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 45 [2018-06-20 23:07:01,047 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-20 23:07:01,048 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:07:01,067 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-20 23:07:01,083 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-20 23:07:01,142 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-20 23:07:01,142 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:07:01,149 INFO ]: Computing forward predicates... [2018-06-20 23:07:01,929 WARN ]: Spent 681.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 48 [2018-06-20 23:07:02,812 WARN ]: Spent 819.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 61 [2018-06-20 23:07:03,184 WARN ]: Spent 317.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 46 [2018-06-20 23:07:07,225 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-20 23:07:07,245 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:07:07,245 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 35 [2018-06-20 23:07:07,246 INFO ]: Interpolant automaton has 35 states [2018-06-20 23:07:07,247 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-20 23:07:07,247 INFO ]: CoverageRelationStatistics Valid=106, Invalid=1084, Unknown=0, NotChecked=0, Total=1190 [2018-06-20 23:07:07,247 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 35 states. [2018-06-20 23:07:09,225 WARN ]: Spent 1.88 s on a formula simplification. DAG size of input: 164 DAG size of output: 89 [2018-06-20 23:07:09,683 WARN ]: Spent 380.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 28 [2018-06-20 23:07:10,378 WARN ]: Spent 610.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 43 [2018-06-20 23:07:10,973 WARN ]: Spent 528.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 50 [2018-06-20 23:07:11,965 WARN ]: Spent 939.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 60 [2018-06-20 23:07:12,795 WARN ]: Spent 777.00 ms on a formula simplification. DAG size of input: 177 DAG size of output: 60 [2018-06-20 23:07:13,390 WARN ]: Spent 461.00 ms on a formula simplification. DAG size of input: 177 DAG size of output: 57 [2018-06-20 23:07:14,044 WARN ]: Spent 589.00 ms on a formula simplification. DAG size of input: 177 DAG size of output: 65 [2018-06-20 23:07:15,213 WARN ]: Spent 1.12 s on a formula simplification. DAG size of input: 171 DAG size of output: 61 [2018-06-20 23:07:17,010 WARN ]: Spent 1.72 s on a formula simplification. DAG size of input: 165 DAG size of output: 86 [2018-06-20 23:07:17,068 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:07:17,068 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-20 23:07:17,068 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-20 23:07:17,068 INFO ]: Start accepts. Automaton has 35 states. Word has length 45 [2018-06-20 23:07:17,069 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:07:17,069 INFO ]: With dead ends: 31 [2018-06-20 23:07:17,069 INFO ]: Without dead ends: 31 [2018-06-20 23:07:17,070 INFO ]: 0 DeclaredPredicates, 76 GetRequests, 31 SyntacticMatches, 2 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 323 ImplicationChecksByTransitivity, 14.1s TimeCoverageRelationStatistics Valid=331, Invalid=1649, Unknown=0, NotChecked=0, Total=1980 [2018-06-20 23:07:17,070 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-20 23:07:17,073 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-20 23:07:17,073 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-20 23:07:17,073 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-20 23:07:17,073 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-20 23:07:17,074 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:07:17,074 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-20 23:07:17,074 INFO ]: Interpolant automaton has 35 states. [2018-06-20 23:07:17,074 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-20 23:07:17,075 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-20 23:07:17,075 INFO ]: Found error trace [2018-06-20 23:07:17,076 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:07:17,076 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:07:17,076 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 10 times [2018-06-20 23:07:17,076 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:07:17,076 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:07:17,076 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:07:17,076 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 23:07:17,076 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:07:17,155 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:07:17,555 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 23 [2018-06-20 23:07:18,012 WARN ]: Spent 153.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 47 [2018-06-20 23:07:18,140 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 47 [2018-06-20 23:07:18,859 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-20 23:07:18,859 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:07:18,859 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 23:07:18,865 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-20 23:07:18,932 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-20 23:07:18,932 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:07:18,947 INFO ]: Computing forward predicates... [2018-06-20 23:07:19,375 WARN ]: Spent 286.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 32 [2018-06-20 23:07:19,799 WARN ]: Spent 358.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 40 Received shutdown request... [2018-06-20 23:07:22,196 WARN ]: Removed 9 from assertion stack [2018-06-20 23:07:22,197 INFO ]: Timeout while computing interpolants [2018-06-20 23:07:22,397 WARN ]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 23:07:22,397 WARN ]: Verification canceled [2018-06-20 23:07:22,401 WARN ]: Timeout [2018-06-20 23:07:22,401 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.06 11:07:22 BoogieIcfgContainer [2018-06-20 23:07:22,401 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-20 23:07:22,402 INFO ]: Toolchain (without parser) took 62128.05 ms. Allocated memory was 311.4 MB in the beginning and 711.5 MB in the end (delta: 400.0 MB). Free memory was 264.8 MB in the beginning and 470.8 MB in the end (delta: -205.9 MB). Peak memory consumption was 488.8 MB. Max. memory is 7.1 GB. [2018-06-20 23:07:22,403 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 311.4 MB. Free memory is still 274.9 MB. There was no memory consumed. Max. memory is 7.1 GB. [2018-06-20 23:07:22,403 INFO ]: ChcToBoogie took 50.72 ms. Allocated memory is still 311.4 MB. Free memory was 264.8 MB in the beginning and 262.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. [2018-06-20 23:07:22,403 INFO ]: Boogie Preprocessor took 60.70 ms. Allocated memory is still 311.4 MB. Free memory was 262.8 MB in the beginning and 261.8 MB in the end (delta: 996.4 kB). Peak memory consumption was 996.4 kB. Max. memory is 7.1 GB. [2018-06-20 23:07:22,404 INFO ]: RCFGBuilder took 221.95 ms. Allocated memory is still 311.4 MB. Free memory was 260.8 MB in the beginning and 252.8 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 7.1 GB. [2018-06-20 23:07:22,404 INFO ]: TraceAbstraction took 61043.49 ms. Allocated memory was 311.4 MB in the beginning and 711.5 MB in the end (delta: 400.0 MB). Free memory was 252.8 MB in the beginning and 470.8 MB in the end (delta: -217.9 MB). Peak memory consumption was 476.8 MB. Max. memory is 7.1 GB. [2018-06-20 23:07:22,407 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 311.4 MB. Free memory is still 274.9 MB. There was no memory consumed. Max. memory is 7.1 GB. * ChcToBoogie took 50.72 ms. Allocated memory is still 311.4 MB. Free memory was 264.8 MB in the beginning and 262.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. * Boogie Preprocessor took 60.70 ms. Allocated memory is still 311.4 MB. Free memory was 262.8 MB in the beginning and 261.8 MB in the end (delta: 996.4 kB). Peak memory consumption was 996.4 kB. Max. memory is 7.1 GB. * RCFGBuilder took 221.95 ms. Allocated memory is still 311.4 MB. Free memory was 260.8 MB in the beginning and 252.8 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 7.1 GB. * TraceAbstraction took 61043.49 ms. Allocated memory was 311.4 MB in the beginning and 711.5 MB in the end (delta: 400.0 MB). Free memory was 252.8 MB in the beginning and 470.8 MB in the end (delta: -217.9 MB). Peak memory consumption was 476.8 MB. Max. memory is 7.1 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 TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 213. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 60.9s OverallTime, 11 OverallIterations, 11 TraceHistogramMax, 29.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 133 SDtfs, 433 SDslu, 930 SDs, 0 SdLazy, 842 SolverSat, 521 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 2.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 433 GetRequests, 217 SyntacticMatches, 11 SemanticMatches, 205 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 882 ImplicationChecksByTransitivity, 42.9s 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.1s SsaConstructionTime, 0.8s SatisfiabilityAnalysisTime, 24.7s InterpolantComputationTime, 531 NumberOfCodeBlocks, 531 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 512 ConstructedInterpolants, 0 QuantifiedInterpolants, 3311336 SizeOfPredicates, 492 NumberOfNonLiveVariables, 1728 ConjunctsInSsa, 494 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/chc-lia-0061.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-20_23-07-22-416.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/chc-lia-0061.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-20_23-07-22-416.csv Completed graceful shutdown