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_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/id_build.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 05:29:27,040 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 05:29:27,068 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 05:29:27,080 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 05:29:27,080 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 05:29:27,081 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 05:29:27,083 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 05:29:27,086 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 05:29:27,089 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 05:29:27,091 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 05:29:27,093 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 05:29:27,094 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 05:29:27,095 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 05:29:27,096 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 05:29:27,097 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 05:29:27,098 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 05:29:27,102 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 05:29:27,104 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 05:29:27,109 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 05:29:27,111 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 05:29:27,112 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 05:29:27,115 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 05:29:27,115 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 05:29:27,115 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 05:29:27,116 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 05:29:27,121 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 05:29:27,122 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 05:29:27,122 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 05:29:27,123 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 05:29:27,123 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 05:29:27,128 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 05:29:27,129 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 05:29:27,129 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 05:29:27,130 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 05:29:27,130 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 05:29:27,131 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 05:29:27,175 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 05:29:27,175 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 05:29:27,175 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 05:29:27,175 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 05:29:27,176 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 05:29:27,177 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 05:29:27,177 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 05:29:27,177 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 05:29:27,177 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:29:27,178 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 05:29:27,178 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 05:29:27,178 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 05:29:27,178 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 05:29:27,178 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 05:29:27,178 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 05:29:27,179 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 05:29:27,179 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 05:29:27,180 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 05:29:27,180 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 05:29:27,270 INFO ]: Repository-Root is: /tmp [2018-06-22 05:29:27,321 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 05:29:27,324 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 05:29:27,325 INFO ]: Initializing SmtParser... [2018-06-22 05:29:27,325 INFO ]: SmtParser initialized [2018-06-22 05:29:27,326 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/id_build.c.smt2 [2018-06-22 05:29:27,345 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 05:29:27,955 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/id_build.c.smt2 unknown [2018-06-22 05:29:28,408 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/id_build.c.smt2 [2018-06-22 05:29:28,413 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 05:29:28,422 INFO ]: Walking toolchain with 4 elements. [2018-06-22 05:29:28,422 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 05:29:28,422 INFO ]: Initializing ChcToBoogie... [2018-06-22 05:29:28,422 INFO ]: ChcToBoogie initialized [2018-06-22 05:29:28,448 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:29:28" (1/1) ... [2018-06-22 05:29:28,511 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:29:28 Unit [2018-06-22 05:29:28,511 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 05:29:28,512 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 05:29:28,512 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 05:29:28,512 INFO ]: Boogie Preprocessor initialized [2018-06-22 05:29:28,529 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:29:28" (1/1) ... [2018-06-22 05:29:28,529 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:29:28" (1/1) ... [2018-06-22 05:29:28,536 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:29:28" (1/1) ... [2018-06-22 05:29:28,537 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:29:28" (1/1) ... [2018-06-22 05:29:28,541 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:29:28" (1/1) ... [2018-06-22 05:29:28,543 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:29:28" (1/1) ... [2018-06-22 05:29:28,545 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:29:28" (1/1) ... [2018-06-22 05:29:28,547 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 05:29:28,547 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 05:29:28,547 INFO ]: Initializing RCFGBuilder... [2018-06-22 05:29:28,547 INFO ]: RCFGBuilder initialized [2018-06-22 05:29:28,548 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:29:28" (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 05:29:28,560 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 05:29:28,560 INFO ]: Found specification of procedure gotoProc [2018-06-22 05:29:28,560 INFO ]: Found implementation of procedure gotoProc [2018-06-22 05:29:28,560 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 05:29:28,560 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 05:29:28,560 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 05:29:28,776 INFO ]: Using library mode [2018-06-22 05:29:28,777 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:29:28 BoogieIcfgContainer [2018-06-22 05:29:28,777 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 05:29:28,778 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 05:29:28,779 INFO ]: Initializing TraceAbstraction... [2018-06-22 05:29:28,782 INFO ]: TraceAbstraction initialized [2018-06-22 05:29:28,782 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:29:28" (1/3) ... [2018-06-22 05:29:28,783 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@407c5adb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 05:29:28, skipping insertion in model container [2018-06-22 05:29:28,783 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:29:28" (2/3) ... [2018-06-22 05:29:28,784 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@407c5adb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 05:29:28, skipping insertion in model container [2018-06-22 05:29:28,784 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:29:28" (3/3) ... [2018-06-22 05:29:28,786 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 05:29:28,795 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 05:29:28,803 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 05:29:28,880 INFO ]: Using default assertion order modulation [2018-06-22 05:29:28,880 INFO ]: Interprodecural is true [2018-06-22 05:29:28,880 INFO ]: Hoare is false [2018-06-22 05:29:28,880 INFO ]: Compute interpolants for FPandBP [2018-06-22 05:29:28,880 INFO ]: Backedges is TWOTRACK [2018-06-22 05:29:28,880 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 05:29:28,880 INFO ]: Difference is false [2018-06-22 05:29:28,880 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 05:29:28,881 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 05:29:28,895 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 05:29:28,904 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 05:29:28,904 INFO ]: Found error trace [2018-06-22 05:29:28,905 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:29:28,905 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:29:28,910 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 05:29:28,912 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:29:28,912 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:29:28,963 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:28,963 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:29:28,963 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:29,002 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:29,172 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:29,175 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 05:29:29,175 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 05:29:29,217 INFO ]: Interpolant automaton has 3 states [2018-06-22 05:29:29,234 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 05:29:29,234 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:29:29,237 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 05:29:29,310 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:29:29,310 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 05:29:29,311 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 05:29:29,312 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 05:29:29,312 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:29:29,324 INFO ]: With dead ends: 9 [2018-06-22 05:29:29,324 INFO ]: Without dead ends: 9 [2018-06-22 05:29:29,327 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:29:29,544 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 05:29:29,615 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 05:29:29,629 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 05:29:29,629 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 05:29:29,631 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 05:29:29,631 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:29:29,631 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 05:29:29,631 INFO ]: Interpolant automaton has 3 states. [2018-06-22 05:29:29,631 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 05:29:29,631 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 05:29:29,631 INFO ]: Found error trace [2018-06-22 05:29:29,631 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:29:29,632 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:29:29,632 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 05:29:29,632 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:29:29,632 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:29:29,633 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:29,633 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:29:29,633 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:29,687 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:29,831 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:29,831 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:29:29,831 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 05:29:29,839 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:29:29,902 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:29,933 INFO ]: Computing forward predicates... [2018-06-22 05:29:30,333 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 6 DAG size of output: 1 [2018-06-22 05:29:30,521 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:30,560 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:29:30,560 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 05:29:30,560 INFO ]: Interpolant automaton has 5 states [2018-06-22 05:29:30,561 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 05:29:30,561 INFO ]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-22 05:29:30,561 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 05:29:30,662 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:29:30,662 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 05:29:30,662 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 05:29:30,662 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 05:29:30,662 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:29:30,663 INFO ]: With dead ends: 10 [2018-06-22 05:29:30,663 INFO ]: Without dead ends: 10 [2018-06-22 05:29:30,664 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-22 05:29:30,664 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 05:29:30,665 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 05:29:30,665 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 05:29:30,665 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 05:29:30,665 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 05:29:30,665 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:29:30,665 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 05:29:30,665 INFO ]: Interpolant automaton has 5 states. [2018-06-22 05:29:30,666 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 05:29:30,667 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 05:29:30,667 INFO ]: Found error trace [2018-06-22 05:29:30,667 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:29:30,667 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:29:30,667 INFO ]: Analyzing trace with hash -2043975570, now seen corresponding path program 2 times [2018-06-22 05:29:30,667 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:29:30,667 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:29:30,668 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:30,668 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:29:30,668 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:30,732 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:30,894 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:30,894 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:29:30,894 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 05:29:30,901 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:29:30,966 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:29:30,966 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:30,970 INFO ]: Computing forward predicates... [2018-06-22 05:29:31,432 WARN ]: Spent 284.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 05:29:33,202 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:33,233 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:29:33,233 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-22 05:29:33,234 INFO ]: Interpolant automaton has 6 states [2018-06-22 05:29:33,234 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 05:29:33,234 INFO ]: CoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:29:33,234 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-22 05:29:33,534 WARN ]: Spent 190.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 05:29:33,573 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:29:33,573 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 05:29:33,573 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 05:29:33,573 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-22 05:29:33,573 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:29:33,573 INFO ]: With dead ends: 11 [2018-06-22 05:29:33,573 INFO ]: Without dead ends: 11 [2018-06-22 05:29:33,574 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2018-06-22 05:29:33,574 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 05:29:33,575 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 05:29:33,575 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 05:29:33,576 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 05:29:33,576 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-22 05:29:33,576 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:29:33,576 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 05:29:33,576 INFO ]: Interpolant automaton has 6 states. [2018-06-22 05:29:33,576 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 05:29:33,576 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 05:29:33,576 INFO ]: Found error trace [2018-06-22 05:29:33,576 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:29:33,576 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:29:33,576 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 3 times [2018-06-22 05:29:33,577 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:29:33,577 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:29:33,577 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:33,577 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:29:33,577 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:33,611 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:33,860 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:33,860 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:29:33,860 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 05:29:33,866 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 05:29:33,930 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 05:29:33,930 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:33,933 INFO ]: Computing forward predicates... [2018-06-22 05:29:35,784 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:35,817 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:29:35,817 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-22 05:29:35,818 INFO ]: Interpolant automaton has 7 states [2018-06-22 05:29:35,818 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 05:29:35,818 INFO ]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-06-22 05:29:35,818 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-22 05:29:35,976 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:29:35,976 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 05:29:35,976 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 05:29:35,976 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-22 05:29:35,976 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:29:35,977 INFO ]: With dead ends: 12 [2018-06-22 05:29:35,977 INFO ]: Without dead ends: 12 [2018-06-22 05:29:35,977 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2018-06-22 05:29:35,977 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 05:29:35,979 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 05:29:35,979 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 05:29:35,979 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 05:29:35,979 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-22 05:29:35,979 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:29:35,979 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 05:29:35,979 INFO ]: Interpolant automaton has 7 states. [2018-06-22 05:29:35,979 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 05:29:35,980 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 05:29:35,980 INFO ]: Found error trace [2018-06-22 05:29:35,980 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:29:35,980 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:29:35,980 INFO ]: Analyzing trace with hash -1433955954, now seen corresponding path program 4 times [2018-06-22 05:29:35,980 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:29:35,980 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:29:35,981 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:35,981 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:29:35,981 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:36,027 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:36,192 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:36,192 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:29:36,192 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 05:29:36,198 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 05:29:36,251 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 05:29:36,251 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:36,254 INFO ]: Computing forward predicates... [2018-06-22 05:29:41,753 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:41,787 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:29:41,787 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-06-22 05:29:41,787 INFO ]: Interpolant automaton has 8 states [2018-06-22 05:29:41,788 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 05:29:41,788 INFO ]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:29:41,788 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 8 states. [2018-06-22 05:29:42,734 WARN ]: Spent 867.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 12 [2018-06-22 05:29:43,634 WARN ]: Spent 795.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 13 [2018-06-22 05:29:43,914 WARN ]: Spent 167.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 05:29:43,972 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:29:43,972 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-22 05:29:43,972 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 05:29:43,972 INFO ]: Start accepts. Automaton has 8 states. Word has length 11 [2018-06-22 05:29:43,972 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:29:43,973 INFO ]: With dead ends: 13 [2018-06-22 05:29:43,973 INFO ]: Without dead ends: 13 [2018-06-22 05:29:43,973 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=58, Invalid=98, Unknown=0, NotChecked=0, Total=156 [2018-06-22 05:29:43,973 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 05:29:43,974 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 05:29:43,974 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 05:29:43,975 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-22 05:29:43,975 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-22 05:29:43,975 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:29:43,975 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-22 05:29:43,975 INFO ]: Interpolant automaton has 8 states. [2018-06-22 05:29:43,975 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-22 05:29:43,975 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 05:29:43,975 INFO ]: Found error trace [2018-06-22 05:29:43,975 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:29:43,976 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:29:43,976 INFO ]: Analyzing trace with hash -1502133097, now seen corresponding path program 5 times [2018-06-22 05:29:43,976 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:29:43,976 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:29:43,977 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:43,977 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:29:43,977 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:44,076 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:44,338 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:44,338 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:29:44,338 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 05:29:44,345 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 05:29:44,399 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-22 05:29:44,399 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:44,403 INFO ]: Computing forward predicates... [2018-06-22 05:29:49,665 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:49,687 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:29:49,687 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2018-06-22 05:29:49,687 INFO ]: Interpolant automaton has 9 states [2018-06-22 05:29:49,687 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 05:29:49,687 INFO ]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2018-06-22 05:29:49,687 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 9 states. [2018-06-22 05:29:50,083 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:29:50,083 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-22 05:29:50,083 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 05:29:50,083 INFO ]: Start accepts. Automaton has 9 states. Word has length 12 [2018-06-22 05:29:50,084 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:29:50,084 INFO ]: With dead ends: 14 [2018-06-22 05:29:50,084 INFO ]: Without dead ends: 14 [2018-06-22 05:29:50,084 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 8 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=70, Invalid=140, Unknown=0, NotChecked=0, Total=210 [2018-06-22 05:29:50,085 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 05:29:50,086 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-22 05:29:50,086 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 05:29:50,086 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-22 05:29:50,086 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-22 05:29:50,087 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:29:50,087 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-22 05:29:50,087 INFO ]: Interpolant automaton has 9 states. [2018-06-22 05:29:50,087 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-22 05:29:50,087 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 05:29:50,087 INFO ]: Found error trace [2018-06-22 05:29:50,087 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:29:50,087 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:29:50,087 INFO ]: Analyzing trace with hash 679342766, now seen corresponding path program 6 times [2018-06-22 05:29:50,087 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:29:50,087 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:29:50,088 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:50,088 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:29:50,088 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:50,198 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:50,450 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:50,450 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:29:50,450 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 05:29:50,467 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 05:29:50,528 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-22 05:29:50,528 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:50,532 INFO ]: Computing forward predicates... [2018-06-22 05:29:53,060 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:53,095 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:29:53,095 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 10 [2018-06-22 05:29:53,096 INFO ]: Interpolant automaton has 10 states [2018-06-22 05:29:53,096 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 05:29:53,096 INFO ]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2018-06-22 05:29:53,096 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 10 states. [2018-06-22 05:29:53,508 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 23 [2018-06-22 05:29:53,509 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:29:53,509 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-22 05:29:53,509 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 05:29:53,509 INFO ]: Start accepts. Automaton has 10 states. Word has length 13 [2018-06-22 05:29:53,510 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:29:53,510 INFO ]: With dead ends: 15 [2018-06-22 05:29:53,510 INFO ]: Without dead ends: 15 [2018-06-22 05:29:53,510 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 51 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=89, Invalid=183, Unknown=0, NotChecked=0, Total=272 [2018-06-22 05:29:53,511 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 05:29:53,512 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 05:29:53,512 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 05:29:53,512 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-22 05:29:53,512 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-06-22 05:29:53,512 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:29:53,512 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-22 05:29:53,512 INFO ]: Interpolant automaton has 10 states. [2018-06-22 05:29:53,512 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-22 05:29:53,513 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 05:29:53,513 INFO ]: Found error trace [2018-06-22 05:29:53,513 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:29:53,513 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:29:53,513 INFO ]: Analyzing trace with hash -414382217, now seen corresponding path program 7 times [2018-06-22 05:29:53,513 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:29:53,513 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:29:53,514 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:53,514 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:29:53,514 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:29:53,567 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:54,191 WARN ]: Spent 381.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-22 05:29:54,649 WARN ]: Spent 382.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 05:29:54,858 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:29:54,858 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:29:54,892 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 05:29:54,899 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:29:54,941 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:29:54,946 INFO ]: Computing forward predicates... [2018-06-22 05:30:03,603 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:30:03,625 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:30:03,625 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 12 [2018-06-22 05:30:03,625 INFO ]: Interpolant automaton has 12 states [2018-06-22 05:30:03,625 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 05:30:03,625 INFO ]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2018-06-22 05:30:03,625 INFO ]: Start difference. First operand 15 states and 15 transitions. Second operand 12 states. [2018-06-22 05:30:03,914 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 28 [2018-06-22 05:30:04,245 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:30:04,245 INFO ]: Finished difference Result 17 states and 17 transitions. [2018-06-22 05:30:04,245 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 05:30:04,245 INFO ]: Start accepts. Automaton has 12 states. Word has length 14 [2018-06-22 05:30:04,245 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:30:04,246 INFO ]: With dead ends: 17 [2018-06-22 05:30:04,246 INFO ]: Without dead ends: 17 [2018-06-22 05:30:04,246 INFO ]: 0 DeclaredPredicates, 32 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=146, Invalid=274, Unknown=0, NotChecked=0, Total=420 [2018-06-22 05:30:04,246 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 05:30:04,248 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 05:30:04,248 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 05:30:04,248 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-06-22 05:30:04,248 INFO ]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 14 [2018-06-22 05:30:04,248 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:30:04,248 INFO ]: Abstraction has 17 states and 17 transitions. [2018-06-22 05:30:04,248 INFO ]: Interpolant automaton has 12 states. [2018-06-22 05:30:04,248 INFO ]: Start isEmpty. Operand 17 states and 17 transitions. [2018-06-22 05:30:04,249 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-22 05:30:04,249 INFO ]: Found error trace [2018-06-22 05:30:04,249 INFO ]: trace histogram [9, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:30:04,249 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:30:04,249 INFO ]: Analyzing trace with hash 1237160535, now seen corresponding path program 8 times [2018-06-22 05:30:04,249 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:30:04,249 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:30:04,250 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:30:04,250 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:30:04,250 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:30:04,364 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:30:04,692 WARN ]: Spent 190.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 05:30:05,100 WARN ]: Spent 360.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 05:30:05,320 INFO ]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:30:05,320 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:30:05,320 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 05:30:05,328 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:30:05,388 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:30:05,388 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:30:05,393 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 05:30:30,577 INFO ]: Timeout while computing interpolants [2018-06-22 05:30:30,778 WARN ]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:30:30,778 WARN ]: Verification canceled [2018-06-22 05:30:30,782 WARN ]: Timeout [2018-06-22 05:30:30,783 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 05:30:30 BoogieIcfgContainer [2018-06-22 05:30:30,783 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 05:30:30,784 INFO ]: Toolchain (without parser) took 62369.98 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 259.7 MB in the beginning and 512.9 MB in the end (delta: -253.1 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 05:30:30,784 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 309.3 MB. Free memory is still 271.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 05:30:30,785 INFO ]: ChcToBoogie took 89.80 ms. Allocated memory is still 309.3 MB. Free memory was 259.7 MB in the beginning and 257.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:30:30,785 INFO ]: Boogie Preprocessor took 34.38 ms. Allocated memory is still 309.3 MB. Free memory was 257.7 MB in the beginning and 255.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:30:30,786 INFO ]: RCFGBuilder took 229.94 ms. Allocated memory is still 309.3 MB. Free memory was 255.8 MB in the beginning and 247.8 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:30:30,786 INFO ]: TraceAbstraction took 62004.29 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 245.8 MB in the beginning and 512.9 MB in the end (delta: -267.1 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 05:30:30,791 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 309.3 MB. Free memory is still 271.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 89.80 ms. Allocated memory is still 309.3 MB. Free memory was 259.7 MB in the beginning and 257.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 34.38 ms. Allocated memory is still 309.3 MB. Free memory was 257.7 MB in the beginning and 255.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 229.94 ms. Allocated memory is still 309.3 MB. Free memory was 255.8 MB in the beginning and 247.8 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 62004.29 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 245.8 MB in the beginning and 512.9 MB in the end (delta: -267.1 MB). Peak memory consumption was 1.3 GB. 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 17 with TraceHistMax 9, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was transforming 0 conjuction. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 61.9s OverallTime, 9 OverallIterations, 9 TraceHistogramMax, 4.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 56 SDtfs, 21 SDslu, 184 SDs, 0 SdLazy, 70 SolverSat, 50 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 154 GetRequests, 52 SyntacticMatches, 26 SemanticMatches, 76 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 207 ImplicationChecksByTransitivity, 7.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=17occurred in iteration=8, 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.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 29.3s InterpolantComputationTime, 161 NumberOfCodeBlocks, 161 NumberOfCodeBlocksAsserted, 24 NumberOfCheckSat, 146 ConstructedInterpolants, 0 QuantifiedInterpolants, 9481 SizeOfPredicates, 28 NumberOfNonLiveVariables, 1260 ConjunctsInSsa, 252 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 0/168 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/id_build.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_05-30-30-801.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/id_build.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_05-30-30-801.csv Completed graceful shutdown