java -Xss4m -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/dillig03.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 12:50:30,835 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 12:50:30,838 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 12:50:30,848 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 12:50:30,849 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 12:50:30,849 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 12:50:30,851 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 12:50:30,852 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 12:50:30,854 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 12:50:30,855 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 12:50:30,856 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 12:50:30,856 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 12:50:30,857 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 12:50:30,858 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 12:50:30,859 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 12:50:30,860 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 12:50:30,861 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 12:50:30,863 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 12:50:30,865 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 12:50:30,866 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 12:50:30,867 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 12:50:30,870 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 12:50:30,870 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 12:50:30,871 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 12:50:30,871 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 12:50:30,872 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 12:50:30,873 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 12:50:30,874 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 12:50:30,875 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 12:50:30,875 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 12:50:30,876 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 12:50:30,877 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 12:50:30,877 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 12:50:30,878 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 12:50:30,879 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 12:50:30,879 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 12:50:30,893 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 12:50:30,893 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 12:50:30,893 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 12:50:30,894 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 12:50:30,895 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 12:50:30,895 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 12:50:30,895 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 12:50:30,895 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 12:50:30,896 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 12:50:30,896 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 12:50:30,896 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 12:50:30,896 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 12:50:30,896 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:50:30,897 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 12:50:30,897 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 12:50:30,897 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 12:50:30,897 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 12:50:30,898 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 12:50:30,898 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 12:50:30,898 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 12:50:30,898 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 12:50:30,900 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 12:50:30,900 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 12:50:30,956 INFO ]: Repository-Root is: /tmp [2018-06-25 12:50:30,973 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 12:50:30,977 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 12:50:30,979 INFO ]: Initializing SmtParser... [2018-06-25 12:50:30,979 INFO ]: SmtParser initialized [2018-06-25 12:50:30,979 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig03.c.smt2 [2018-06-25 12:50:30,981 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-25 12:50:31,071 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig03.c.smt2 unknown [2018-06-25 12:50:31,508 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig03.c.smt2 [2018-06-25 12:50:31,513 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 12:50:31,521 INFO ]: Walking toolchain with 4 elements. [2018-06-25 12:50:31,521 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 12:50:31,521 INFO ]: Initializing ChcToBoogie... [2018-06-25 12:50:31,521 INFO ]: ChcToBoogie initialized [2018-06-25 12:50:31,525 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:50:31" (1/1) ... [2018-06-25 12:50:31,580 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:50:31 Unit [2018-06-25 12:50:31,580 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 12:50:31,581 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 12:50:31,581 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 12:50:31,581 INFO ]: Boogie Preprocessor initialized [2018-06-25 12:50:31,603 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:50:31" (1/1) ... [2018-06-25 12:50:31,603 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:50:31" (1/1) ... [2018-06-25 12:50:31,609 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:50:31" (1/1) ... [2018-06-25 12:50:31,609 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:50:31" (1/1) ... [2018-06-25 12:50:31,613 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:50:31" (1/1) ... [2018-06-25 12:50:31,614 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:50:31" (1/1) ... [2018-06-25 12:50:31,615 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:50:31" (1/1) ... [2018-06-25 12:50:31,624 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 12:50:31,625 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 12:50:31,625 INFO ]: Initializing RCFGBuilder... [2018-06-25 12:50:31,625 INFO ]: RCFGBuilder initialized [2018-06-25 12:50:31,626 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:50:31" (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) [2018-06-25 12:50:31,644 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 12:50:31,644 INFO ]: Found specification of procedure gotoProc [2018-06-25 12:50:31,644 INFO ]: Found implementation of procedure gotoProc [2018-06-25 12:50:31,644 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 12:50:31,644 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 12:50:31,644 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:50:31,859 INFO ]: Using library mode [2018-06-25 12:50:31,859 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:50:31 BoogieIcfgContainer [2018-06-25 12:50:31,859 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 12:50:31,870 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 12:50:31,870 INFO ]: Initializing TraceAbstraction... [2018-06-25 12:50:31,873 INFO ]: TraceAbstraction initialized [2018-06-25 12:50:31,873 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:50:31" (1/3) ... [2018-06-25 12:50:31,874 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4b80e4a4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 12:50:31, skipping insertion in model container [2018-06-25 12:50:31,875 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:50:31" (2/3) ... [2018-06-25 12:50:31,875 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4b80e4a4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 12:50:31, skipping insertion in model container [2018-06-25 12:50:31,875 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:50:31" (3/3) ... [2018-06-25 12:50:31,877 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 12:50:31,896 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 12:50:31,912 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 12:50:32,002 INFO ]: Using default assertion order modulation [2018-06-25 12:50:32,002 INFO ]: Interprodecural is true [2018-06-25 12:50:32,002 INFO ]: Hoare is false [2018-06-25 12:50:32,002 INFO ]: Compute interpolants for FPandBP [2018-06-25 12:50:32,003 INFO ]: Backedges is TWOTRACK [2018-06-25 12:50:32,003 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 12:50:32,003 INFO ]: Difference is false [2018-06-25 12:50:32,003 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 12:50:32,003 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 12:50:32,031 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 12:50:32,042 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 12:50:32,043 INFO ]: Found error trace [2018-06-25 12:50:32,043 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:50:32,044 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:50:32,053 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 12:50:32,055 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:50:32,056 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:50:32,091 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:32,091 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:50:32,091 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:32,128 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:32,186 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:32,188 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 12:50:32,189 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 12:50:32,190 INFO ]: Interpolant automaton has 3 states [2018-06-25 12:50:32,202 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 12:50:32,202 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:50:32,204 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 12:50:32,255 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:50:32,255 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 12:50:32,256 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 12:50:32,257 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 12:50:32,257 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:50:32,263 INFO ]: With dead ends: 9 [2018-06-25 12:50:32,264 INFO ]: Without dead ends: 9 [2018-06-25 12:50:32,265 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:50:32,281 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 12:50:32,309 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 12:50:32,311 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 12:50:32,311 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 12:50:32,312 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 12:50:32,313 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:50:32,313 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 12:50:32,313 INFO ]: Interpolant automaton has 3 states. [2018-06-25 12:50:32,313 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 12:50:32,313 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 12:50:32,313 INFO ]: Found error trace [2018-06-25 12:50:32,313 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:50:32,313 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:50:32,313 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 12:50:32,313 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:50:32,313 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:50:32,315 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:32,315 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:50:32,315 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:32,347 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:32,453 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:32,453 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:50:32,454 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-25 12:50:32,461 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:50:32,505 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:32,511 INFO ]: Computing forward predicates... [2018-06-25 12:50:32,853 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:32,883 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:50:32,902 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 12:50:32,903 INFO ]: Interpolant automaton has 5 states [2018-06-25 12:50:32,903 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 12:50:32,903 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 12:50:32,904 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 12:50:32,953 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:50:32,953 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 12:50:32,953 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 12:50:32,953 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 12:50:32,953 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:50:32,954 INFO ]: With dead ends: 10 [2018-06-25 12:50:32,954 INFO ]: Without dead ends: 10 [2018-06-25 12:50:32,955 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:50:32,955 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 12:50:32,956 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 12:50:32,956 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 12:50:32,956 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 12:50:32,956 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 12:50:32,956 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:50:32,957 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 12:50:32,957 INFO ]: Interpolant automaton has 5 states. [2018-06-25 12:50:32,957 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 12:50:32,957 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 12:50:32,957 INFO ]: Found error trace [2018-06-25 12:50:32,957 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:50:32,957 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:50:32,957 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 12:50:32,957 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:50:32,957 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:50:32,959 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:32,959 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:50:32,959 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:33,026 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:33,341 WARN ]: Spent 115.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-25 12:50:33,342 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:33,342 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:50:33,342 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-25 12:50:33,365 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 12:50:33,434 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:50:33,434 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:33,437 INFO ]: Computing forward predicates... [2018-06-25 12:50:34,318 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:34,337 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:50:34,338 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-25 12:50:34,338 INFO ]: Interpolant automaton has 6 states [2018-06-25 12:50:34,338 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 12:50:34,338 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:50:34,338 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-25 12:50:34,369 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:50:34,369 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 12:50:34,370 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 12:50:34,370 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-25 12:50:34,370 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:50:34,370 INFO ]: With dead ends: 11 [2018-06-25 12:50:34,370 INFO ]: Without dead ends: 11 [2018-06-25 12:50:34,370 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2018-06-25 12:50:34,371 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 12:50:34,372 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 12:50:34,372 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 12:50:34,372 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 12:50:34,372 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 12:50:34,373 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:50:34,373 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 12:50:34,373 INFO ]: Interpolant automaton has 6 states. [2018-06-25 12:50:34,373 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 12:50:34,373 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 12:50:34,373 INFO ]: Found error trace [2018-06-25 12:50:34,373 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:50:34,373 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:50:34,373 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-25 12:50:34,373 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:50:34,373 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:50:34,375 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:34,375 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:50:34,375 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:34,412 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:34,698 WARN ]: Spent 191.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-25 12:50:34,891 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:34,891 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:50:34,891 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-25 12:50:34,899 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 12:50:34,960 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 12:50:34,960 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:34,964 INFO ]: Computing forward predicates... [2018-06-25 12:50:35,835 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:35,857 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:50:35,857 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-25 12:50:35,857 INFO ]: Interpolant automaton has 7 states [2018-06-25 12:50:35,857 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 12:50:35,857 INFO ]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2018-06-25 12:50:35,857 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-25 12:50:36,120 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:50:36,120 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 12:50:36,120 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 12:50:36,120 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-25 12:50:36,120 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:50:36,121 INFO ]: With dead ends: 12 [2018-06-25 12:50:36,121 INFO ]: Without dead ends: 12 [2018-06-25 12:50:36,121 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=45, Invalid=65, Unknown=0, NotChecked=0, Total=110 [2018-06-25 12:50:36,121 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 12:50:36,122 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 12:50:36,122 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 12:50:36,123 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 12:50:36,123 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 12:50:36,123 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:50:36,123 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 12:50:36,123 INFO ]: Interpolant automaton has 7 states. [2018-06-25 12:50:36,123 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 12:50:36,123 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 12:50:36,123 INFO ]: Found error trace [2018-06-25 12:50:36,124 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:50:36,124 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:50:36,124 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 4 times [2018-06-25 12:50:36,124 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:50:36,124 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:50:36,125 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:36,125 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:50:36,125 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:36,175 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:36,345 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:36,346 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:50:36,346 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-25 12:50:36,352 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 12:50:36,375 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 12:50:36,376 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:36,378 INFO ]: Computing forward predicates... [2018-06-25 12:50:43,110 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:43,135 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:50:43,135 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2018-06-25 12:50:43,135 INFO ]: Interpolant automaton has 9 states [2018-06-25 12:50:43,135 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-25 12:50:43,135 INFO ]: CoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2018-06-25 12:50:43,135 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 9 states. [2018-06-25 12:50:43,333 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:50:43,333 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-25 12:50:43,333 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 12:50:43,333 INFO ]: Start accepts. Automaton has 9 states. Word has length 11 [2018-06-25 12:50:43,333 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:50:43,333 INFO ]: With dead ends: 13 [2018-06-25 12:50:43,333 INFO ]: Without dead ends: 13 [2018-06-25 12:50:43,334 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=70, Invalid=112, Unknown=0, NotChecked=0, Total=182 [2018-06-25 12:50:43,334 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-25 12:50:43,335 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-25 12:50:43,335 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-25 12:50:43,335 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-25 12:50:43,335 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-25 12:50:43,335 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:50:43,335 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-25 12:50:43,335 INFO ]: Interpolant automaton has 9 states. [2018-06-25 12:50:43,335 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-25 12:50:43,336 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-25 12:50:43,336 INFO ]: Found error trace [2018-06-25 12:50:43,336 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:50:43,336 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:50:43,336 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 5 times [2018-06-25 12:50:43,336 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:50:43,336 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:50:43,337 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:43,337 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:50:43,337 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:43,406 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:43,985 WARN ]: Spent 256.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 16 [2018-06-25 12:50:44,024 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:44,024 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:50:44,025 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-25 12:50:44,031 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 12:50:44,077 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 12:50:44,077 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:44,080 INFO ]: Computing forward predicates... [2018-06-25 12:50:48,496 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:48,519 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:50:48,519 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2018-06-25 12:50:48,519 INFO ]: Interpolant automaton has 10 states [2018-06-25 12:50:48,519 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-25 12:50:48,519 INFO ]: CoverageRelationStatistics Valid=32, Invalid=58, Unknown=0, NotChecked=0, Total=90 [2018-06-25 12:50:48,519 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 10 states. [2018-06-25 12:50:48,792 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:50:48,792 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-25 12:50:48,792 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 12:50:48,792 INFO ]: Start accepts. Automaton has 10 states. Word has length 12 [2018-06-25 12:50:48,792 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:50:48,792 INFO ]: With dead ends: 14 [2018-06-25 12:50:48,792 INFO ]: Without dead ends: 14 [2018-06-25 12:50:48,793 INFO ]: 0 DeclaredPredicates, 24 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=79, Invalid=131, Unknown=0, NotChecked=0, Total=210 [2018-06-25 12:50:48,793 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-25 12:50:48,794 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-25 12:50:48,794 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-25 12:50:48,794 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-25 12:50:48,794 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-25 12:50:48,794 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:50:48,794 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-25 12:50:48,794 INFO ]: Interpolant automaton has 10 states. [2018-06-25 12:50:48,794 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-25 12:50:48,794 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-25 12:50:48,794 INFO ]: Found error trace [2018-06-25 12:50:48,794 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:50:48,794 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:50:48,795 INFO ]: Analyzing trace with hash 23503628, now seen corresponding path program 6 times [2018-06-25 12:50:48,795 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:50:48,795 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:50:48,795 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:48,795 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:50:48,795 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:48,865 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:49,124 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:49,125 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:50:49,125 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-25 12:50:49,132 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 12:50:49,184 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-25 12:50:49,184 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:49,187 INFO ]: Computing forward predicates... [2018-06-25 12:50:57,860 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:50:57,891 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:50:57,891 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 13 [2018-06-25 12:50:57,891 INFO ]: Interpolant automaton has 13 states [2018-06-25 12:50:57,891 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-25 12:50:57,891 INFO ]: CoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2018-06-25 12:50:57,891 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 13 states. [2018-06-25 12:50:58,054 WARN ]: Spent 145.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 14 [2018-06-25 12:50:58,450 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:50:58,450 INFO ]: Finished difference Result 16 states and 16 transitions. [2018-06-25 12:50:58,450 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-25 12:50:58,450 INFO ]: Start accepts. Automaton has 13 states. Word has length 13 [2018-06-25 12:50:58,450 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:50:58,450 INFO ]: With dead ends: 16 [2018-06-25 12:50:58,450 INFO ]: Without dead ends: 16 [2018-06-25 12:50:58,451 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 77 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=144, Invalid=276, Unknown=0, NotChecked=0, Total=420 [2018-06-25 12:50:58,451 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-25 12:50:58,452 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-25 12:50:58,452 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-25 12:50:58,452 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-06-25 12:50:58,452 INFO ]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 13 [2018-06-25 12:50:58,452 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:50:58,452 INFO ]: Abstraction has 16 states and 16 transitions. [2018-06-25 12:50:58,452 INFO ]: Interpolant automaton has 13 states. [2018-06-25 12:50:58,452 INFO ]: Start isEmpty. Operand 16 states and 16 transitions. [2018-06-25 12:50:58,452 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-25 12:50:58,452 INFO ]: Found error trace [2018-06-25 12:50:58,452 INFO ]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:50:58,453 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:50:58,453 INFO ]: Analyzing trace with hash 1051911180, now seen corresponding path program 7 times [2018-06-25 12:50:58,453 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:50:58,453 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:50:58,453 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:58,453 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:50:58,453 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:50:58,531 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:50:59,164 WARN ]: Spent 396.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 8 [2018-06-25 12:51:00,050 WARN ]: Spent 816.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 17 [2018-06-25 12:51:00,200 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:00,201 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:51:00,201 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-25 12:51:00,217 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:51:00,273 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:00,277 INFO ]: Computing forward predicates... [2018-06-25 12:51:00,640 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:00,656 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:00,678 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:00,686 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:00,695 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:00,704 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:00,706 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 12:51:00,738 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:00,753 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 12:51:00,782 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:02,411 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:02,419 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:02,422 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:08,241 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:08,259 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:08,269 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:08,269 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:14,342 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:14,521 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 12:51:14,685 WARN ]: expecting exponential blowup for input size 12 [2018-06-25 12:51:14,734 WARN ]: Simplifying disjunction of 7600 conjuctions. This might take some time... [2018-06-25 12:51:15,240 INFO ]: Simplified to disjunction of 688 conjuctions. [2018-06-25 12:51:15,302 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:15,312 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:15,333 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:15,412 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:15,433 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:15,505 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:15,574 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 12:51:15,612 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:15,635 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:15,818 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-25 12:51:34,449 INFO ]: Timeout while computing interpolants [2018-06-25 12:51:34,649 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:51:34,650 WARN ]: Verification canceled [2018-06-25 12:51:34,653 WARN ]: Timeout [2018-06-25 12:51:34,653 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 12:51:34 BoogieIcfgContainer [2018-06-25 12:51:34,653 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 12:51:34,654 INFO ]: Toolchain (without parser) took 63140.17 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 263.7 MB in the beginning and 241.0 MB in the end (delta: 22.7 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-25 12:51:34,654 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 12:51:34,655 INFO ]: ChcToBoogie took 59.64 ms. Allocated memory is still 309.3 MB. Free memory was 263.7 MB in the beginning and 261.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:51:34,655 INFO ]: Boogie Preprocessor took 42.89 ms. Allocated memory is still 309.3 MB. Free memory was 261.7 MB in the beginning and 260.7 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-25 12:51:34,656 INFO ]: RCFGBuilder took 234.98 ms. Allocated memory is still 309.3 MB. Free memory was 260.7 MB in the beginning and 251.7 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:51:34,656 INFO ]: TraceAbstraction took 62783.16 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 251.7 MB in the beginning and 241.0 MB in the end (delta: 10.8 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-25 12:51:34,662 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 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 59.64 ms. Allocated memory is still 309.3 MB. Free memory was 263.7 MB in the beginning and 261.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 42.89 ms. Allocated memory is still 309.3 MB. Free memory was 261.7 MB in the beginning and 260.7 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 234.98 ms. Allocated memory is still 309.3 MB. Free memory was 260.7 MB in the beginning and 251.7 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 62783.16 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 251.7 MB in the beginning and 241.0 MB in the end (delta: 10.8 MB). Peak memory consumption was 1.4 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 16 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 32791 quantified variables from 12 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 62.6s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 1.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 49 SDtfs, 15 SDslu, 136 SDs, 0 SdLazy, 57 SolverSat, 36 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 124 GetRequests, 45 SyntacticMatches, 15 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 167 ImplicationChecksByTransitivity, 3.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=16occurred in iteration=7, 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, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 23.9s InterpolantComputationTime, 133 NumberOfCodeBlocks, 133 NumberOfCodeBlocksAsserted, 22 NumberOfCheckSat, 120 ConstructedInterpolants, 0 QuantifiedInterpolants, 6151 SizeOfPredicates, 24 NumberOfNonLiveVariables, 780 ConjunctsInSsa, 190 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 0/112 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/dillig03.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_12-51-34-680.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig03.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_12-51-34-680.csv Completed graceful shutdown