java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/hsortprime.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:08:25,842 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:08:25,844 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:08:25,856 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:08:25,856 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:08:25,858 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:08:25,859 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:08:25,863 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:08:25,864 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:08:25,866 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:08:25,866 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:08:25,867 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:08:25,867 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:08:25,868 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:08:25,871 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:08:25,872 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:08:25,874 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:08:25,875 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:08:25,877 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:08:25,878 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:08:25,887 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:08:25,890 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:08:25,890 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:08:25,890 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:08:25,891 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:08:25,891 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:08:25,892 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:08:25,892 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:08:25,893 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:08:25,893 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:08:25,894 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:08:25,894 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:08:25,894 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:08:25,895 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:08:25,896 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:08:25,896 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 15:08:25,919 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:08:25,919 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:08:25,920 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:08:25,920 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:08:25,924 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:08:25,924 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:08:25,925 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:08:25,925 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:08:25,925 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:08:25,925 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:08:25,926 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:08:25,926 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:08:25,926 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:08:25,926 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:08:25,926 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:08:25,927 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:08:25,927 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:08:25,927 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:08:25,927 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:08:25,929 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:08:25,929 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:08:25,978 INFO ]: Repository-Root is: /tmp [2018-06-22 15:08:25,995 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:08:26,001 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:08:26,003 INFO ]: Initializing SmtParser... [2018-06-22 15:08:26,003 INFO ]: SmtParser initialized [2018-06-22 15:08:26,004 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/hsortprime.c.smt2 [2018-06-22 15:08:26,006 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 15:08:26,096 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/hsortprime.c.smt2 unknown [2018-06-22 15:08:26,498 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/hsortprime.c.smt2 [2018-06-22 15:08:26,503 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:08:26,510 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:08:26,510 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:08:26,510 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:08:26,510 INFO ]: ChcToBoogie initialized [2018-06-22 15:08:26,513 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:08:26" (1/1) ... [2018-06-22 15:08:26,560 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:08:26 Unit [2018-06-22 15:08:26,560 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:08:26,563 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:08:26,563 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:08:26,563 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:08:26,585 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:08:26" (1/1) ... [2018-06-22 15:08:26,585 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:08:26" (1/1) ... [2018-06-22 15:08:26,604 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:08:26" (1/1) ... [2018-06-22 15:08:26,604 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:08:26" (1/1) ... [2018-06-22 15:08:26,611 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:08:26" (1/1) ... [2018-06-22 15:08:26,612 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:08:26" (1/1) ... [2018-06-22 15:08:26,614 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:08:26" (1/1) ... [2018-06-22 15:08:26,617 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:08:26,617 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:08:26,617 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:08:26,617 INFO ]: RCFGBuilder initialized [2018-06-22 15:08:26,618 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:08:26" (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 15:08:26,629 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:08:26,630 INFO ]: Found specification of procedure False [2018-06-22 15:08:26,630 INFO ]: Found implementation of procedure False [2018-06-22 15:08:26,630 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:08:26,630 INFO ]: Found specification of procedure state [2018-06-22 15:08:26,630 INFO ]: Found implementation of procedure state [2018-06-22 15:08:26,630 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:08:26,630 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:08:26,630 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 15:08:26,855 INFO ]: Using library mode [2018-06-22 15:08:26,856 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:08:26 BoogieIcfgContainer [2018-06-22 15:08:26,856 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:08:26,857 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:08:26,857 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:08:26,863 INFO ]: TraceAbstraction initialized [2018-06-22 15:08:26,863 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:08:26" (1/3) ... [2018-06-22 15:08:26,864 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4a0d8177 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:08:26, skipping insertion in model container [2018-06-22 15:08:26,864 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:08:26" (2/3) ... [2018-06-22 15:08:26,864 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4a0d8177 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:08:26, skipping insertion in model container [2018-06-22 15:08:26,864 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:08:26" (3/3) ... [2018-06-22 15:08:26,866 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:08:26,876 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:08:26,886 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:08:26,934 INFO ]: Using default assertion order modulation [2018-06-22 15:08:26,937 INFO ]: Interprodecural is true [2018-06-22 15:08:26,937 INFO ]: Hoare is false [2018-06-22 15:08:26,937 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:08:26,937 INFO ]: Backedges is TWOTRACK [2018-06-22 15:08:26,937 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:08:26,937 INFO ]: Difference is false [2018-06-22 15:08:26,937 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:08:26,937 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:08:26,954 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:08:26,966 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:08:26,967 INFO ]: Found error trace [2018-06-22 15:08:26,967 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:08:26,968 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:08:26,973 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 15:08:26,975 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:08:26,976 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:08:27,020 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:27,020 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:08:27,020 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:27,056 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:27,242 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:08:27,245 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:08:27,245 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:08:27,256 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:08:27,281 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:08:27,282 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:08:27,284 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:08:27,410 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:08:27,410 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:08:27,410 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:08:27,411 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:08:27,412 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:08:27,421 INFO ]: With dead ends: 13 [2018-06-22 15:08:27,421 INFO ]: Without dead ends: 13 [2018-06-22 15:08:27,422 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:08:27,440 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:08:27,462 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:08:27,463 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:08:27,464 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:08:27,465 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:08:27,465 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:08:27,465 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:08:27,465 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:08:27,465 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:08:27,466 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:08:27,466 INFO ]: Found error trace [2018-06-22 15:08:27,467 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:08:27,467 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:08:27,467 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 15:08:27,467 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:08:27,467 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:08:27,468 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:27,468 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:08:27,468 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:27,536 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:27,843 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:08:27,843 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:08:27,843 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 15:08:27,853 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:08:27,910 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:27,918 INFO ]: Computing forward predicates... [2018-06-22 15:08:28,230 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:08:28,264 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:08:28,264 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 15:08:28,264 INFO ]: Interpolant automaton has 6 states [2018-06-22 15:08:28,265 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 15:08:28,265 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:08:28,265 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-22 15:08:28,470 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:08:28,470 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:08:28,471 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:08:28,471 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-22 15:08:28,472 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:08:28,472 INFO ]: With dead ends: 15 [2018-06-22 15:08:28,472 INFO ]: Without dead ends: 15 [2018-06-22 15:08:28,473 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:08:28,473 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:08:28,475 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:08:28,475 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:08:28,478 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:08:28,478 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:08:28,478 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:08:28,478 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:08:28,479 INFO ]: Interpolant automaton has 6 states. [2018-06-22 15:08:28,479 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:08:28,479 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:08:28,479 INFO ]: Found error trace [2018-06-22 15:08:28,479 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:08:28,479 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:08:28,479 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 15:08:28,479 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:08:28,479 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:08:28,480 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:28,480 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:08:28,480 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:28,573 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:29,024 WARN ]: Spent 231.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 10 [2018-06-22 15:08:29,499 WARN ]: Spent 458.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 19 [2018-06-22 15:08:29,612 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:08:29,612 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:08:29,612 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 15:08:29,621 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:08:29,683 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:08:29,684 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:29,687 INFO ]: Computing forward predicates... [2018-06-22 15:08:30,151 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:08:30,170 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:08:30,170 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-22 15:08:30,170 INFO ]: Interpolant automaton has 8 states [2018-06-22 15:08:30,170 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 15:08:30,170 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-22 15:08:30,171 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 8 states. [2018-06-22 15:08:30,344 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:08:30,344 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:08:30,345 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:08:30,345 INFO ]: Start accepts. Automaton has 8 states. Word has length 17 [2018-06-22 15:08:30,345 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:08:30,346 INFO ]: With dead ends: 17 [2018-06-22 15:08:30,346 INFO ]: Without dead ends: 17 [2018-06-22 15:08:30,346 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 16 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2018-06-22 15:08:30,346 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:08:30,349 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:08:30,349 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:08:30,349 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:08:30,350 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:08:30,350 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:08:30,350 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:08:30,350 INFO ]: Interpolant automaton has 8 states. [2018-06-22 15:08:30,350 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:08:30,350 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:08:30,350 INFO ]: Found error trace [2018-06-22 15:08:30,350 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:08:30,351 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:08:30,351 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 15:08:30,351 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:08:30,351 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:08:30,352 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:30,352 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:08:30,352 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:30,396 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:30,749 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 27 [2018-06-22 15:08:30,924 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:08:30,924 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:08:30,954 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) [2018-06-22 15:08:30,963 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:08:31,016 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:08:31,016 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:31,021 INFO ]: Computing forward predicates... [2018-06-22 15:08:31,328 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:08:31,359 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:08:31,359 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-22 15:08:31,359 INFO ]: Interpolant automaton has 10 states [2018-06-22 15:08:31,359 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 15:08:31,359 INFO ]: CoverageRelationStatistics Valid=25, Invalid=65, Unknown=0, NotChecked=0, Total=90 [2018-06-22 15:08:31,360 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 10 states. [2018-06-22 15:08:31,614 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 31 [2018-06-22 15:08:31,897 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:08:31,897 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:08:31,898 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:08:31,898 INFO ]: Start accepts. Automaton has 10 states. Word has length 21 [2018-06-22 15:08:31,898 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:08:31,899 INFO ]: With dead ends: 19 [2018-06-22 15:08:31,899 INFO ]: Without dead ends: 19 [2018-06-22 15:08:31,899 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 18 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:08:31,899 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:08:31,903 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:08:31,903 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:08:31,903 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:08:31,903 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:08:31,903 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:08:31,903 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:08:31,903 INFO ]: Interpolant automaton has 10 states. [2018-06-22 15:08:31,904 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:08:31,904 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:08:31,904 INFO ]: Found error trace [2018-06-22 15:08:31,904 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:08:31,904 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:08:31,905 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 15:08:31,905 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:08:31,905 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:08:31,905 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:31,905 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:08:31,905 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:31,977 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:33,900 WARN ]: Spent 1.66 s on a formula simplification. DAG size of input: 43 DAG size of output: 16 [2018-06-22 15:08:34,082 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 33 [2018-06-22 15:08:34,293 WARN ]: Spent 203.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 37 [2018-06-22 15:08:34,555 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:08:34,555 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:08:34,555 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 15:08:34,562 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:08:34,629 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:08:34,629 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:34,635 INFO ]: Computing forward predicates... [2018-06-22 15:08:40,604 WARN ]: Spent 5.43 s on a formula simplification. DAG size of input: 726 DAG size of output: 72 [2018-06-22 15:08:43,642 WARN ]: Spent 2.76 s on a formula simplification. DAG size of input: 54 DAG size of output: 27 [2018-06-22 15:08:45,947 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:08:45,967 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:08:45,967 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2018-06-22 15:08:45,967 INFO ]: Interpolant automaton has 19 states [2018-06-22 15:08:45,967 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 15:08:45,968 INFO ]: CoverageRelationStatistics Valid=63, Invalid=279, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:08:45,968 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 19 states. [2018-06-22 15:08:46,993 WARN ]: Spent 976.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 95 [2018-06-22 15:08:47,556 WARN ]: Spent 433.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 36 [2018-06-22 15:08:48,176 WARN ]: Spent 597.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 50 [2018-06-22 15:08:48,530 WARN ]: Spent 322.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 69 [2018-06-22 15:08:49,351 WARN ]: Spent 798.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 83 [2018-06-22 15:08:49,381 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:08:49,381 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:08:49,383 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:08:49,383 INFO ]: Start accepts. Automaton has 19 states. Word has length 25 [2018-06-22 15:08:49,383 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:08:49,383 INFO ]: With dead ends: 21 [2018-06-22 15:08:49,383 INFO ]: Without dead ends: 21 [2018-06-22 15:08:49,384 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 18 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 15.0s TimeCoverageRelationStatistics Valid=130, Invalid=422, Unknown=0, NotChecked=0, Total=552 [2018-06-22 15:08:49,384 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:08:49,386 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:08:49,386 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:08:49,387 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:08:49,387 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:08:49,387 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:08:49,387 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:08:49,387 INFO ]: Interpolant automaton has 19 states. [2018-06-22 15:08:49,387 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:08:49,388 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:08:49,388 INFO ]: Found error trace [2018-06-22 15:08:49,388 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:08:49,388 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:08:49,388 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 15:08:49,388 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:08:49,388 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:08:49,389 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:49,389 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:08:49,389 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:49,472 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:49,858 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 14 [2018-06-22 15:08:50,290 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 32 [2018-06-22 15:08:50,539 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:08:50,539 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:08:50,539 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 15:08:50,545 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:08:50,651 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:08:50,651 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:50,657 INFO ]: Computing forward predicates... [2018-06-22 15:08:53,409 WARN ]: Spent 2.18 s on a formula simplification. DAG size of input: 503 DAG size of output: 36 [2018-06-22 15:08:53,822 WARN ]: Spent 352.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 28 [2018-06-22 15:08:54,343 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:08:54,363 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:08:54,363 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 19 [2018-06-22 15:08:54,363 INFO ]: Interpolant automaton has 19 states [2018-06-22 15:08:54,363 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 15:08:54,363 INFO ]: CoverageRelationStatistics Valid=60, Invalid=282, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:08:54,363 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 19 states. [2018-06-22 15:08:54,730 WARN ]: Spent 337.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 53 [2018-06-22 15:08:55,102 WARN ]: Spent 238.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 28 [2018-06-22 15:08:55,434 WARN ]: Spent 288.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 30 [2018-06-22 15:08:55,699 WARN ]: Spent 142.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 31 [2018-06-22 15:08:55,744 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:08:55,744 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:08:55,744 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:08:55,744 INFO ]: Start accepts. Automaton has 19 states. Word has length 29 [2018-06-22 15:08:55,744 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:08:55,745 INFO ]: With dead ends: 23 [2018-06-22 15:08:55,745 INFO ]: Without dead ends: 23 [2018-06-22 15:08:55,745 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 21 SyntacticMatches, 4 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 92 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=139, Invalid=461, Unknown=0, NotChecked=0, Total=600 [2018-06-22 15:08:55,745 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:08:55,748 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:08:55,748 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:08:55,749 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:08:55,749 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:08:55,750 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:08:55,750 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:08:55,750 INFO ]: Interpolant automaton has 19 states. [2018-06-22 15:08:55,750 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:08:55,750 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:08:55,750 INFO ]: Found error trace [2018-06-22 15:08:55,750 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:08:55,751 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:08:55,751 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 15:08:55,751 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:08:55,751 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:08:55,751 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:55,751 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:08:55,751 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:08:55,849 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:56,628 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:08:56,629 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:08:56,629 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 15:08:56,635 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:08:56,728 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:08:56,728 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:08:56,734 INFO ]: Computing forward predicates... [2018-06-22 15:08:56,855 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:08:56,907 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:08:57,122 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:08:57,211 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:08:57,261 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:08:57,376 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:08:57,460 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:08:57,553 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:08:57,849 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:08:57,900 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:08:58,089 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:08:58,102 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:08:58,152 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:08:58,289 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:08:58,300 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:08:58,407 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:01,399 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:01,442 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:01,627 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:01,632 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:01,659 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:01,832 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:01,838 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:01,928 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:02,098 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:02,123 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:02,262 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:02,268 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:02,294 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:02,486 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:02,492 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:02,590 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:02,806 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:02,833 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:03,008 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:03,012 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:03,040 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:03,223 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:03,228 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:03,312 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:03,490 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:03,518 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:03,696 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:03,701 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:03,729 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:03,959 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:03,965 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:04,073 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:05,254 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:05,279 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:09:05,372 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:09:05,426 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:05,452 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:09:05,573 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:09:05,591 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:05,663 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:05,830 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:05,856 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:09:05,957 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:09:05,961 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:05,987 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:09:06,088 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:09:06,094 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:06,154 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:07,129 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:07,171 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:07,385 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:07,392 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:07,422 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:07,582 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:07,589 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:07,685 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:08,253 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:08,299 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:09:08,445 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:09:08,484 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:08,510 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:09:08,631 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:09:08,646 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:08,720 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:08,887 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:08,915 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:09,121 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:09,126 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:09,154 WARN ]: Simplifying disjunction of 7353 conjuctions. This might take some time... [2018-06-22 15:09:09,325 INFO ]: Simplified to disjunction of 218 conjuctions. [2018-06-22 15:09:09,331 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:09,426 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:09,894 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:09,920 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:09:10,031 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:09:10,035 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:10,062 WARN ]: Simplifying disjunction of 5889 conjuctions. This might take some time... [2018-06-22 15:09:10,156 INFO ]: Simplified to disjunction of 147 conjuctions. [2018-06-22 15:09:10,162 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:10,232 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 15:09:10,764 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 15:09:10,958 WARN ]: Simplifying disjunction of 29942 conjuctions. This might take some time... [2018-06-22 15:09:12,574 INFO ]: Simplified to disjunction of 340 conjuctions. [2018-06-22 15:09:12,581 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 15:09:12,715 WARN ]: Simplifying disjunction of 29942 conjuctions. This might take some time... [2018-06-22 15:09:14,242 INFO ]: Simplified to disjunction of 340 conjuctions. [2018-06-22 15:09:14,249 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 15:09:14,351 WARN ]: Simplifying disjunction of 20320 conjuctions. This might take some time... [2018-06-22 15:09:14,966 INFO ]: Simplified to disjunction of 274 conjuctions. [2018-06-22 15:09:14,971 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 15:09:15,111 WARN ]: Simplifying disjunction of 20320 conjuctions. This might take some time... [2018-06-22 15:09:15,968 INFO ]: Simplified to disjunction of 274 conjuctions. [2018-06-22 15:09:16,147 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 15:09:16,281 WARN ]: Simplifying disjunction of 29942 conjuctions. This might take some time... [2018-06-22 15:09:17,887 INFO ]: Simplified to disjunction of 340 conjuctions. [2018-06-22 15:09:17,893 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 15:09:18,030 WARN ]: Simplifying disjunction of 29942 conjuctions. This might take some time... [2018-06-22 15:09:19,641 INFO ]: Simplified to disjunction of 340 conjuctions. [2018-06-22 15:09:19,647 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 15:09:19,804 WARN ]: Simplifying disjunction of 20320 conjuctions. This might take some time... [2018-06-22 15:09:20,645 INFO ]: Simplified to disjunction of 274 conjuctions. [2018-06-22 15:09:20,653 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 15:09:20,750 WARN ]: Simplifying disjunction of 20320 conjuctions. This might take some time... [2018-06-22 15:09:21,615 INFO ]: Simplified to disjunction of 274 conjuctions. [2018-06-22 15:09:23,290 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 15:09:23,441 WARN ]: Simplifying disjunction of 38376 conjuctions. This might take some time... [2018-06-22 15:09:25,485 INFO ]: Simplified to disjunction of 482 conjuctions. [2018-06-22 15:09:25,494 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 15:09:25,647 WARN ]: Simplifying disjunction of 38376 conjuctions. This might take some time... [2018-06-22 15:09:28,392 INFO ]: Simplified to disjunction of 482 conjuctions. [2018-06-22 15:09:28,400 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 15:09:28,507 WARN ]: Simplifying disjunction of 25534 conjuctions. This might take some time... Received shutdown request... [2018-06-22 15:09:28,723 INFO ]: Timeout while computing interpolants [2018-06-22 15:09:28,924 WARN ]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:09:28,924 WARN ]: Verification canceled [2018-06-22 15:09:28,928 WARN ]: Timeout [2018-06-22 15:09:28,928 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:09:28 BoogieIcfgContainer [2018-06-22 15:09:28,928 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:09:28,929 INFO ]: Toolchain (without parser) took 62426.18 ms. Allocated memory was 303.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 249.0 MB in the beginning and 867.4 MB in the end (delta: -618.4 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 15:09:28,930 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 303.6 MB. Free memory is still 269.0 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:09:28,931 INFO ]: ChcToBoogie took 50.48 ms. Allocated memory is still 303.6 MB. Free memory was 249.0 MB in the beginning and 247.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:09:28,931 INFO ]: Boogie Preprocessor took 54.06 ms. Allocated memory is still 303.6 MB. Free memory was 247.0 MB in the beginning and 245.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:09:28,932 INFO ]: RCFGBuilder took 238.71 ms. Allocated memory is still 303.6 MB. Free memory was 245.0 MB in the beginning and 230.9 MB in the end (delta: 14.0 MB). Peak memory consumption was 14.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:09:28,932 INFO ]: TraceAbstraction took 62071.36 ms. Allocated memory was 303.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 230.9 MB in the beginning and 867.4 MB in the end (delta: -636.4 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 15:09:28,940 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 303.6 MB. Free memory is still 269.0 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 50.48 ms. Allocated memory is still 303.6 MB. Free memory was 249.0 MB in the beginning and 247.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 54.06 ms. Allocated memory is still 303.6 MB. Free memory was 247.0 MB in the beginning and 245.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 238.71 ms. Allocated memory is still 303.6 MB. Free memory was 245.0 MB in the beginning and 230.9 MB in the end (delta: 14.0 MB). Peak memory consumption was 14.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 62071.36 ms. Allocated memory was 303.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 230.9 MB in the beginning and 867.4 MB in the end (delta: -636.4 MB). Peak memory consumption was 1.2 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 34 with TraceHistMax 7, while TraceCheckSpWp was constructing forward predicates, while DnfTransformerHelper was XNF transformer was simplifying 25534 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 62.0s OverallTime, 7 OverallIterations, 7 TraceHistogramMax, 5.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 71 SDtfs, 88 SDslu, 275 SDs, 0 SdLazy, 234 SolverSat, 111 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 171 GetRequests, 89 SyntacticMatches, 11 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 200 ImplicationChecksByTransitivity, 22.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=23occurred in iteration=6, 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, 6 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 21.8s InterpolantComputationTime, 219 NumberOfCodeBlocks, 219 NumberOfCodeBlocksAsserted, 20 NumberOfCheckSat, 208 ConstructedInterpolants, 0 QuantifiedInterpolants, 2713292 SizeOfPredicates, 271 NumberOfNonLiveVariables, 1460 ConjunctsInSsa, 196 ConjunctsInUnsatCore, 11 InterpolantComputations, 1 PerfectInterpolantSequences, 70/250 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/hsortprime.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-09-28-951.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/hsortprime.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-09-28-951.csv Completed graceful shutdown